Problem 1114. -- 菜哭武的面试题

1114: 菜哭武的面试题

Time Limit: 4 Sec  Memory Limit: 512 MB
Submit: 37  Solved: 11
[Submit][Status][Web Board]

Description

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

限制每种操作的使用次数,序列中的hi可以被改为任意整数(可以是负数),求最小代价,无解输出-1。

Input

第一行一个整数T,表示有T组测试数据。(1 T 4)
然后每组有M+2行:
第一行,两个整数N,M;(N,M  200)
第二行,N个整数hi(hi 106)
接下来m行,每行格式为opi, li, ci空格隔开,其中opi为一个字符,表示这种操作是+1 还是-1。(li N, ci  106)

Output

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

Sample Input

第一组输入:
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

Sample Output

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


第二组输入:
Case #1:
96

HINT

Source

[Submit][Status]