你是一位强大的巫师，正在穿越 Aarelia 王国。你的旅途经过一片陡峭的丘陵和山脉。山区可以表示为 $n$ 个区域的序列；每个区域都有其海拔 $h_i$。

不幸的是，你没有任何登山装备（坦白说，也没有登山技巧），而且你的飞行法术也已经耗尽。然而，当区域海拔形成一个非递减序列时，你将能够穿越该区域，即对于从 $1$ 到 $(n - 1)$ 的每个 $i$，都有 $h_i \le h_{i+1}$（你是从右向左行进的，高处的跌落对你没有威胁）。

唯一能帮助你的法术是“地震术”。该法术影响若干相邻的区域，并允许你改变它们的海拔。你知道 $m$ 种地震术；每种法术都有其作用范围 $l_i$（即受法术影响的相邻区域数量）、能量消耗 $c_i$，并且可以将所有受影响区域的海拔升高或降低 $1$（单个法术可以被施放以升高或降低区域海拔，但不能同时进行）。每种法术都可以应用于区域内任何长度为 $l_i$ 的区间，并且可以无限次施放（每次重复施放都需要支付能量消耗）。施放法术后，某些区域的海拔可能会变为负数。

确定是否可以通过改变地形使你能够安全地穿越该区域，如果可以，请找出你必须花费的最低总能量。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $m$ ($1 \le n, m \le 200$)。

第二行包含 $n$ 个空格分隔的整数 $h_i$ —— 区域的初始海拔 ($0 \le h_i \le 10^6$)。

接下来的 $m$ 行描述了你所知道的地震术种类。第 $i$ 行描述了法术种类，格式为 “$t_i \ l_i \ c_i$”；其中 $t_i$ 是字符 “+”（如果该法术允许将海拔升高 $1$）或 “-”（如果该法术允许将海拔降低 $1$）；$l_i$ 和 $c_i$ 分别是法术的作用范围和能量消耗 ($1 \le l_i \le n, 1 \le c_i \le 10^6$)。

输出格式

如果可以穿越该区域，请打印必须花费的最低总能量，否则打印 $-1$。

样例

样例输入 1

3 2
3 2 1
+ 1 1
- 1 1

样例输出 1

2

样例输入 2

3 1
3 2 1
+ 2 1

样例输出 2

-1