[JDWOI-1] 蜀道难

蜀道难，难于上青天…… 蜀道之所以难，就是因为山路崎岖不平。

小 K 和小 M 也模拟了蜀道难。在蜀道难中，有 $n$ 座山，每座山高度为 $h_i$。小 K 和小 M 有 $m$ 种魔法，每一次膜法可以把连续 $l_i$ 座山的高度抬高或压低 $1$，同时消耗 $c_i$ 点体力。 现在，小 K 和小 M 想让蜀道难的 $n$ 座山的高度不下降，这样蜀道就不难了。请问他们最少需消耗多少体力？ **注**：所有时候山的高度都不能为负。

第一行两个整数 $n,m$，表示山的数量和膜法数量。 第二行 $n$ 个整数 $h_i$，表示山的高度。 接下来 $m$ 行，每行一个字符和两个整数 $w_i, l_i, c_i$，描述一种膜法（如果 $w_i$ 为 $+$，代表抬高；如果 $w_i$ 为 $-$，代表压低）。

一行一个整数，表示最小消耗的体力。 如果无解，输出 $-1$。

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

1

### 样例解释 使用 $1$ 体力值将第三座山升高 $1$。 ### 数据范围 - 对于 $10\%$ 的数据，$1\leq n,m \leq 10$； - 对于另外 $30\%$ 的数据，$1\leq n,m \leq 20$； - 对于另外 $10\%$ 的数据，$m=1$； - 对于所有的数据，$1\leq n, m \leq 200$，$1\leq l_i \leq n$，$1\leq h_i, c_i \leq 10^3$。