Description

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.

Input Format

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 Format

Output one integer, representing the minimum stamina cost.

If there is no solution, output $-1$.

3 3
1 3 2
- 1 10
- 2 3
+ 1 1

1

Hint

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