You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

割绳子的游戏主角是一只叫Om-Nom的小怪兽。巧合的是他也是今天的问题的主角。

一天Om-Nom拜访他的老朋友春神（因为春神家里有糖），春神有两种糖（春糖和水果糖）一共$n$颗。i-th糖悬吊在天花板上离地$H_i$米，并且它的甜蜜值是$m_i$。Om-Nom想尽可能地多吃糖，最开始的时候Om-Nom只能跳$x$米高，当他吃了甜蜜值为$m_i$的糖，它可以跳的高度就增加$m_i$米。

Om-Nom最多可以吃多少颗糖，Can you tell me?他从不吃两个连续相同类型的糖果，因为他觉得那太无聊了。

输入格式

第一行输入一个数字T，代表输入数据有T组$(T \le 1000)$ 每组第一行输入两个整数$n,x(1 ≤ n, x ≤ 2000)$春神的糖果数量和Om初始跳跃高度。 接下来的$n$行每行输入$t_i,h_i,m_i(0 ≤ t_i ≤ 1; 1 ≤ h_i, m_i ≤ 2000)$表示第$i$颗糖的类型，高度，甜蜜值。

输出格式

针对每组数据分别输出Om最多可以吃多少糖.

1
5 3
0 2 4
1 3 1
0 8 3
0 20 10
1 5 5

4