luogu#P7730. [JDWOI-1] 蜀道难
[JDWOI-1] 蜀道难
题目背景
蜀道难,难于上青天……
蜀道之所以难,就是因为山路崎岖不平。
题目描述
小 K 和小 M 也模拟了蜀道难。在蜀道难中,有 座山,每座山高度为 。小 K 和小 M 有 种魔法,每一次膜法可以把连续 座山的高度抬高或压低 ,同时消耗 点体力。
现在,小 K 和小 M 想让蜀道难的 座山的高度不下降,这样蜀道就不难了。请问他们最少需消耗多少体力?
注:所有时候山的高度都不能为负。
输入格式
第一行两个整数 ,表示山的数量和膜法数量。
第二行 个整数 ,表示山的高度。
接下来 行,每行一个字符和两个整数 ,描述一种膜法(如果 为 ,代表抬高;如果 为 ,代表压低)。
输出格式
一行一个整数,表示最小消耗的体力。
如果无解,输出 。
3 3
1 3 2
- 1 10
- 2 3
+ 1 1
1
提示
样例解释
使用 体力值将第三座山升高 。
数据范围
- 对于 的数据,;
- 对于另外 的数据,;
- 对于另外 的数据,;
- 对于所有的数据,,,。