题目描述

割绳子游戏的主人公是一个名叫 Om Nom 的小怪物。他喜欢糖果。真巧他也是今天问题的主人公。

一天，Om Nom去拜访他的朋友Even。Even有两类糖果(水果糖和焦糖糖) $n$ 颗，其中 $i$ 颗糖果挂在离房子地板 $h_i$ 厘米高的地方，它的质量是 $m_i$ 。Om Nom想吃掉尽可能多的糖果。开始时，Om Nom最多只能跳高 $x$ 厘米。当Om Nom吃了一颗质量为 $y$ 的糖果后，他的力气变大了，跳跃的高度也增加了 $y$ 厘米。

如果Om Nom从不连续吃两颗相同类型的糖果(Om Nom觉得太无聊了)，他最多可以吃多少颗糖果？

输入描述

第一行包含两个整数： $n$ 和 $x$ 。 $1 \le n \le 2000$ - Even拥有的糖果数量和 Om Nom 跳跃的初始高度。

下面 $n$ 行中的每一行都包含三个整数 $t_i , h_i , m_i$ - 第 $i$ 个糖果的类型、高度和质量。如果数字 $t_i$ 等于 0，则当前糖果为焦糖糖块，否则为水果糖块。

输出描述

打印一个整数 - Om Nom 最多能吃的糖果数量。

样例数据

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

4

Note

4 糖果的一种可能吃法是按顺序吃： 1 , 5 , 3 , 2 .让我们假设以下情况：

1. 最初，Om Nom跳跃的高度等于 3 。他可以够到糖果 1 和 2 。假设他吃了 1 粒糖果。由于这颗糖果的质量等于 4 ，他跳跃的高度将上升到 3 + 4 = 7 。
2. 现在，Om Nom可以到达糖果 2 和 5 。假设他吃了糖果 5 。那么他跳跃的高度将是 7 + 5 = 12 。
3. 此时，Om Nom可以够到两颗糖果，分别是 2 和 3 。他不会吃 2 糖果，因为它的类型与之前吃过的糖果的类型一致。Om Nom吃了糖果 3 ，他跳跃的高度是 12 + 3 = 15 。
4. Om Nom吃了糖果 2 ，他跳跃的高度是 15 + 1 = 16 。他无法到达糖果 4 。