P7730 [JDWOI-1] Shu Road Is Hard

Shu Road Is Hard, harder than climbing to the sky... The reason the Shu roads are hard is that the mountain paths are rough and uneven.

Little K and Little M also simulated the difficulty of the Shu roads. In this Shu Road Is Hard setting, there are $n$ mountains, and the height of the $i$-th mountain is $h_i$. Little K and Little M have $m$ types of magic. Each time they use a type of magic, they can increase or decrease the heights of a consecutive segment of $l_i$ mountains by $1$, and it costs $c_i$ stamina points. Now, Little K and Little M want the heights of the $n$ mountains in Shu Road Is Hard to be non-decreasing, so that the road will no longer be hard. What is the minimum stamina cost? **Note**: The height of any mountain can never be negative at any time.

The first line contains two integers $n, m$, representing the number of mountains and the number of magic types. The second line contains $n$ integers $h_i$, representing the heights of the mountains. The next $m$ lines each contain one character and three integers $w_i, l_i, c_i$, describing one type of magic (if $w_i$ is $+$, it means increasing; if $w_i$ is $-$, it means decreasing).

Output one integer, representing the minimum stamina cost. If there is no solution, output $-1$.

### Sample Explanation Use $1$ stamina point to increase the third mountain by $1$. ### Constraints - For $10\%$ of the testdata, $1 \leq n, m \leq 10$. - For another $30\%$ of the testdata, $1 \leq n, m \leq 20$. - For another $10\%$ of the testdata, $m = 1$. - For all testdata, $1 \leq n, m \leq 200$, $1 \leq l_i \leq n$, $1 \leq h_i, c_i \leq 10^3$. Translated by ChatGPT 5