Fruit Ninja I
I thought you must have played Fruit Ninja on the android or iOS. As we all know, it's a very amusing and popular game. But after a long time, Smallrain was so tired of playing it. So he surfed on the Internet for finding a new one. Finally he found that there was another Fruit Ninja on www.acmer.org which made him so crazy. The rule of this game was very strange. Aha, let me tell you:
1. The fruit always appeared on the top of screen, and then fell vertically toward the bottom in 1 second, disappeared finally. The speed of cutting fruit is so fast that you can ignore it. But you should notice that you can only cut fruit horizontally, and every second you can cut only one time. At the same time, the track of cutting fruits must be continuous.
2. There are good fruits and bad fruits. When you cut a good one, you'll gain one point; oppositely you'll lose one point. Notice that, on your track of cutting, every continuous three or more good fruits will make you gain double points for extra rewards.
As a crazy gamer, Smallrain want to gain more points, but once he cut one time, he won't cut in the next m seconds. For example, if you cut fruit on the 1st second and m equals to 5, then you cannot cut again between 2nd and 6th (inclusion). Because he thought only in this way he can conserve his energy to play it in a whole day or more days. Can you help him?
There are multiple test cases. The first line of input contains a single integer T (T <= 100) denoting the number of test cases.
For each case, the first line has two integers: n and m denotes the number of fruits and interval described above. (0 < n, m <= 10000)
Each of the follow n lines contains three integers t (the second of the fruit appeared), s ("0" means good fruit, "1" means bad one), and p (p, the position of the fruit appeared on the top of screen). (1 <= t <= 10000, 1 <= p < =200)
Notice: there are not two fruits appearing in the same position at the same time.
For each test case, output the case number first. And then output a line with the maximum points.
2 3 3 1 0 1 2 0 2 3 0 3 10 1 1 0 1 1 0 2 1 1 3 2 0 1 3 0 1 3 0 2 3 1 3 3 0 4 3 0 5 3 0 6
Case 1: 1 Case 2: 9
(1 0 1)(1 0 2) for 2 score.
(3 0 1)(3 0 2)(3 1 3)(3 0 4)(3 0 5)(3 0 6) for 2 - 1 + 2 * 3 = 7 score