问题描述

新格尔公司的天才程序员菜哭武最近在担任面试官，他今天出了这样一个题目。给出一个长度为 $N$ 的整数序列 $h_i$，现在要通过一些操作将这个序列修改为单调不降序列，即 $h_i \leq h_{i+1}$。可以用的操作有 $M$ 种，第 $i$ 种操作可以通过支付 $c_i$ 的代价将一段长度恰为 $l_i$ 的连续子序列 $+1$ 或 $-1$（由对应的操作符确定是 $+1$ 还是 $-1$，具体参考输入格式）。

不限制每种操作的使用次数，序列中的 $h_i$ 可以被改为任意整数（可以是负数），求最小代价，无解输出 $-1$。

输入格式

第一行一个整数 $T$，表示有 $T$ 组测试数据。（$1 \leq T \leq 4$）
然后每组有 $M + 2$ 行：
第一行，两个整数 $N, M$；（$N, M \leq 200$）
第二行，$N$ 个整数 $h_i$（$h_i \leq 10^6$）
接下来 $M$ 行，每行格式为 $op_i\ l_i\ c_i$ 空格隔开，其中 $op_i$ 为一个字符，表示这种操作是 $+1$ 还是 $-1$。（$l_i \leq N$，$1 \leq c_i \leq 10^6$）

输出格式

对于每组数据，第一行输出 Case #x:（$x$ 编号从 1 开始）。
第二行是一个整数，代表最小代价，若无解输出 $-1$。

样例输入

第一组输入：
2
3 2
3 2 1
+ 1 1
- 1 1
3 1
3 2 1
+ 2 1

第二组输入：
1
10 10
23 1 8 14 2 3 15 50 53 53
+ 4 6
- 1 10
+ 2 4
+ 4 2
- 3 5
+ 1 2
+ 3 2
+ 5 7
- 1 6
+ 4 5

样例输出

第一组输入：
Case #1:
2
Case #2:
-1

第二组输入：
Case #1:
96