A. Feed with Candy
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Главный герой игры Cut the Rope — монстрик Ом Ном, который очень любит конфеты. По случайному совпадению, он же главный герой этой задачи.

Как-то раз Ом Ном зашел в гости к своему другу Эвану. В доме Эвана есть n конфет двух типов (леденцы и карамельки), i-я конфета висит на высоте hi сантиметров от пола дома и имеет массу mi. Ом Ном хочет съесть как можно больше конфет. В начале Ом Ном может прыгать не более, чем на x сантиметров в высоту. Когда Ом Ном съедает конфету массы y, он становится сильнее, и высота его прыжка увеличивается на y сантиметров.

Какое максимальное количество конфет сможет съесть Ом Ном, если он никогда не будет есть подряд две конфеты одного и того же типа (Ом Ном считает, что это слишком скучно)?

Входные данные

В первой строке записаны два целых числа n и x (1 ≤ n, x ≤ 2000) — количество конфет в доме Эвана и начальная высота прыжка Ом Нома.

В каждой из следующих n строк записаны три целых числа ti, hi, mi (0 ≤ ti ≤ 1; 1 ≤ hi, mi ≤ 2000) — тип, высота и масса i-й конфеты. Если число ti равно 0, то текущая конфета — это карамелька, иначе текущая конфета — это леденец.

Выходные данные

Выведите единственное целое число — максимальное количество конфет, которое сможет съесть Ом Ном.

Примеры
Входные данные
5 3
0 2 4
1 3 1
0 8 3
0 20 10
1 5 5
Выходные данные
4
Примечание

Один из возможных способов съесть 4 конфеты — есть конфеты в порядке: 1, 5, 3, 2. Рассмотрим подробнее такое развитие событий:

  1. Изначально высота прыжка Ом Нома равна 3. Он может допрыгнуть до конфет 1 и 2. Допустим, что он съест конфету 1. Так как масса этой конфеты равна 4, высота его прыжка станет равна 3 + 4 = 7.
  2. Теперь Ом Ном может допрыгнуть до конфет 2 и 5. Допустим, что он съест конфету 5. Тогда высота его прыжка станет равна 7 + 5 = 12.
  3. В данный момент Ом Ном может допрыгнуть до двух конфет: 2 и 3. Есть конфету 2 он не будет, так как ее тип совпадает с предыдущей съеденной конфетой. Ом Ном съедает конфету 3, высота его прыжка становится равна 12 + 3 = 15.
  4. Ом Ном съедает конфету 2, высота его прыжка становится равна 15 + 1 = 16. До конфеты 4 он допрыгнуть не может.