← 返回题目列表

Codeforces · 436/A

A. 用糖果喂食

中文机器翻译题面 查看原题

割绳子游戏的英雄是一个名叫 Om Nom 的小怪物。他喜欢糖果。多么巧合啊!他也是今天问题的英雄。

有一天,Om Nom 拜访了他的朋友 Evan。埃文有 n 颗两种类型的糖果(水果滴和焦糖滴),第 i 颗糖果悬挂在距离房子地板 hi 厘米的高度,其质量为 mi。 Om Nom 想吃尽可能多的糖果。一开始,Om Nom 最多可以跳 x 厘米高。当 Om Nom 吃下质量为 y 的糖果时,他会变得更强壮,跳跃高度也会增加 y 厘米。

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

输入

第一行包含两个整数,n 和 x (1 ≤ n, x ≤ 2000) — Evan 拥有的糖果数量以及 Om Nom 跳跃的初始高度。

以下 n 行中的每一行包含三个整数 ti, hi, mi (0 ≤ ti ≤ 1; 1 ≤ hi, mi ≤ 2000) — 第 i 颗糖果的类型、高度和质量。如果数字ti等于0,则当前糖果是焦糖滴,否则是水果滴。

输出

打印一个整数——Om Nom 可以吃的最大糖果数量。

示例

输入 #1

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

输出 #1

4

注意

吃 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。