Minimum Coins for Floor Advancement

You are given a building with \(N+1\) floors labeled from \(1\) to \(N+1\) and \(M\) players labeled from \(1\) to \(M\). For each \(i\) from \(1\) to \(N\), moving from floor \(i\) to floor \(i+1\) requires \(A_i\) units of energy. You can only move upward (from floor \(i\) to floor \(i+1\)).

Each floor from \(1\) to \(N\) contains a shop. At the shop on floor \(i\), you can pay \(B_i\) coins to gain \(1\) unit of energy. You can use the shop any number of times on that floor, but your energy cannot exceed your personal energy cap. For the \(j\)-th player the energy cap is \(U_j\) and each player starts with \(0\) energy.

Initially, the \(j\)-th player is on floor \(S_j\), and his goal is to reach floor \(T_j\). Determine the minimum number of coins needed for each player to reach his destination, or report that it is impossible.

Note: When a player moves from floor \(i\) to floor \(i+1\), he must have at least \(A_i\) energy units, which will be deducted from his current energy. Energy can only be purchased on floors \(1\) to \(N\), and the cost per unit varies by floor.

inputFormat

The first line contains two integers \(N\) and \(M\) \( (1 \leq N, M)\) describing the number of floors with shops and the number of players.

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\), where \(A_i\) is the energy required to move from floor \(i\) to floor \(i+1\).

The third line contains \(N\) integers \(B_1, B_2, \dots, B_N\), where \(B_i\) is the coin cost to get one unit of energy at the shop on floor \(i\).

Then \(M\) lines follow. Each of these lines contains three integers \(S_j, T_j, U_j\) representing the starting floor, destination floor, and the energy cap for the \(j\)-th player.

outputFormat

Output \(M\) lines. For each player, output the minimum number of coins required to reach his destination. If it is impossible to reach the destination, output -1.

sample

3 3
3 1 2
2 3 1
1 4 5
2 4 4
1 3 3

11
5
9