题目背景

蜀道难，难于上青天……

蜀道之所以难，就是因为山路崎岖不平。

题目描述

小 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$。