Problem Description
There are n boxes in one line numbered 1 to n, at the beginning, all boxes are black. Two kinds of operations are provided to you:
1 ai xi ：You can choose any xi black boxes in interval [1,ai], and color them white;
2 ai xi ：You can choose any xi black boxes in interval [ai,n], and color them white;
lcq wants to know if she use these operations in optimal strategy, the maximum number of white boxes she can get, and if she get maximum white boxes, the minimum number of operations she should use.
Tips:
1. It is obvious that sometimes you can choose not to use some operations.
2. If the interval of one operation didn’t have enough black boxes, you can’t use this operation.
Input
The first line contains one integer T, indicating the number of test case.
The first line of each test case contains two integers N (1 <= N <= 1000) and M (1<=M<=1000), indicating that there are N grids and M operations in total. Then M lines followed, each of which contains three integers si(1<=si<=2) , ai and xi (0 <= xi <= N,1<=ai<=N), si indicating the type of this operation, ai and xi indicating that the interval is [1,ai] or ai,n, and you can choose xi black boxes and color them white.
Output
For each test case, output case number first. Then output two integers, the first one is the maximum boxes she can get, the second one is the minimum operations she should use.
Sample Input
1
5 2
2 3 3
1 3 3
Sample Output
Case 1: 3 1
http://blog.csdn.net/jtjy568805874/article/details/52174354
在一行中有n个盒子，编号为1到n，开始时，所有的盒子都是黑色的。两种操作提供给你：
1 ai XI：你可以在区间1中选择任何XI黑盒，并把它们涂成白色；
2 ai XI：你可以选择区间中的任何XI黑盒，并将它们涂成白色；
LCQ想知道她是否使用这些操作的最优策略，她可以得到最大的白盒数，如果她获得最大的白盒，操作的最小数目她应该用。
提示:
1。很明显，有时您可以选择不使用某些操作。
2。如果一个操作的间隔没有足够的黑盒，则不能使用此操作。
输入
第一行包含一个整数t，表示测试用例的数量。
每个测试用例的第一行包含两个整数n（1 < = n＝1000）和m（1 < = < = 1000），表示总共有n个网格和m个操作。然后m行跟随，每一个包含三个整数SI（1 < = < = 2），ai和XI（0 < = < = n，1＝= n = n），SI指示该操作的类型，ai和XI表示间隔为[ 1，ai ]或ai，n，您可以选择XI黑盒并将它们着色。
输出
对于每个测试用例，输出案例号为第一。然后输出两个整数，第一个是她能得到的最大盒子，第二个是她应该使用的最小运算量。
样本输入
一
5 2
2 3 3
1 3 3
示例输出
案例1：3 1