luogu#P7730. [JDWOI-1] 蜀道难

[JDWOI-1] 蜀道难

题目背景

蜀道难,难于上青天……

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

题目描述

小 K 和小 M 也模拟了蜀道难。在蜀道难中,有 nn 座山,每座山高度为 hih_i。小 K 和小 M 有 mm 种魔法,每一次膜法可以把连续 lil_i 座山的高度抬高或压低 11,同时消耗 cic_i 点体力。

现在,小 K 和小 M 想让蜀道难的 nn 座山的高度不下降,这样蜀道就不难了。请问他们最少需消耗多少体力?

:所有时候山的高度都不能为负。

输入格式

第一行两个整数 n,mn,m,表示山的数量和膜法数量。

第二行 nn 个整数 hih_i,表示山的高度。

接下来 mm 行,每行一个字符和两个整数 wi,li,ciw_i, l_i, c_i,描述一种膜法(如果 wiw_i++,代表抬高;如果 wiw_i-,代表压低)。

输出格式

一行一个整数,表示最小消耗的体力。

如果无解,输出 1-1

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

提示

样例解释

使用 11 体力值将第三座山升高 11

数据范围

  • 对于 10%10\% 的数据,1n,m101\leq n,m \leq 10
  • 对于另外 30%30\% 的数据,1n,m201\leq n,m \leq 20
  • 对于另外 10%10\% 的数据,m=1m=1
  • 对于所有的数据,1n,m2001\leq n, m \leq 2001lin1\leq l_i \leq n1hi,ci1031\leq h_i, c_i \leq 10^3