P7408 [JOI 2021 Final] Dungeon 3 / Dungeon 3

There is a building with $N+1$ floors, numbered $1 \sim N+1$. There are $M$ people, numbered $1 \sim M$. Moving from floor $i$ to floor $i+1$ costs $A_i$ energy, and you can only move from floor $i$ to floor $i+1$, not the other way around. From floor $1$ to floor $N$, there is a shop on each floor. At the shop on floor $i$, you can pay $B_i$ coins to increase your energy by $1$. You may use the shop multiple times, but you cannot make your energy exceed your energy cap. The energy cap of person $j$ is $U_j$. Everyone starts with energy $0$. Person $j$ starts on floor $S_j$, and they want to reach floor $T_j$. For each person, answer the minimum number of coins needed to reach their destination, or state that it is impossible.

The first line contains two integers $N, M$, representing the number of floors and the number of people. The second line contains $N$ integers $A_i$, representing the energy required to move. The third line contains $N$ integers $B_i$, representing the number of coins needed to buy energy at each floor’s shop. The next $M$ lines each contain three integers $S_j, T_j, U_j$, describing one person.

Output $M$ lines. Each line contains one integer, representing the minimum number of coins person $j$ needs to reach floor $T_j$. If they cannot move to floor $T_j$, output $-1$.

#### Explanation of Sample 1 Person $1$ cannot reach floor $3$. Person $2$ can reach floor $6$ in the following way: - On floor $1$, spend $8$ coins to make their energy $4$. - Move to floor $2$, and the energy becomes $1$. - On floor $2$, spend $15$ coins to make their energy $4$. - Move to floor $3$, and the energy becomes $0$. - On floor $3$, spend $4$ coins to make their energy $4$. - Move to floor $4$, and the energy becomes $3$. - Move to floor $5$, and the energy becomes $2$. - On floor $5$, spend $2$ coins to make their energy $4$. - Move to floor $6$. In total, $29$ coins are needed. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (11 pts): $N, M \le 3000$. - Subtask 2 (14 pts): All $U_j$ are equal. - Subtask 3 (31 pts): $T_j = N+1$. - Subtask 4 (44 pts): No special constraints. For $100\%$ of the testdata, $1 \le N, M, A_i, B_i \le 2 \times 10^5$, $1 \le S_j < T_j \le N+1$, $1 \le U_j \le 10^9$. #### Notes Translated from [The 20th Japanese Olympiad in Informatics Final Round E ダンジョン 3 English translation Dungeon 3](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t5-en.pdf). Translated by ChatGPT 5