P3859 [TJOI2008] Thief

A famous thief enters a storage room full of gems. This storage is a chain of rooms, numbered from $0$. To enter room $i$, one must come from room $i-1$, as shown in the figure. 

The figure above shows the case of three rooms. The black parts are the doors connecting two adjacent rooms, numbered from left to right as $0,1,2\cdots$. When the thief enters the storage through door $0$, the timing system starts, and each door has its own closing time. Each room contains different kinds of gems. For each kind of gem, its value and the time the thief spends to take one are different. To simplify the problem, we assume the time to move between rooms is negligible, and the quantities of every kind of gem in all rooms are unlimited. What is the maximum total value of gems the thief can obtain while still being able to escape successfully? Note: For each door, the thief must exit through it strictly before it closes.

For each test case, the first line contains two integers $N$ and $M$, representing that the storage has $N$ rooms and there are $M$ kinds of gems. The second line contains $N$ positive integers, where the $i$-th integer denotes the closing time of door $i$ (doors are numbered from $0$). The next $M$ lines each contain three integers $r$, $v$ and $t$, meaning that this kind of gem is located in room $r$, its value is $v$, and it takes time $t$ for the thief to take one.

Output the maximum total value of gems the thief can obtain while successfully escaping the storage.

### Sample Explanation Although the gem worth $5$ in room $2$ looks good, it is better to take two gems worth $3$, and then take two gems worth $1$ in room $0$, for a total value of $8$. ### Constraints and Conventions For $100\%$ of the testdata, the number of rooms does not exceed $50$, the closing time of each door does not exceed $1000$, the number of gem types does not exceed $100$, and each value does not exceed $1000$. Translated by ChatGPT 5