В одной из версий игры «Манчкин» в наборе есть $$$n$$$ монстров. Для каждого из них можно определить его агрессивность. Агрессивность $$$i$$$-го монстра будет равна $$$a_i$$$, если количество монстров у игрока не превышает $$$c_i$$$, иначе агрессивность равна $$$b_i$$$ ($$$a_i \le b_i$$$).
По правилам игры суммарная агрессивность монстров, которые находятся у игрока не может превышать $$$s$$$.
Игроки внимательно следят за соблюдением правил игры другими участниками. Поэтому они хотят знать, какое максимально возможное количество монстров может быть у одного игрока.
В первой строке через пробел заданы два целых числа $$$n$$$ и $$$s$$$ ($$$1 \le n \le 10^5, 0 \le s \le 10^9$$$) — количество монстров и максимальная возможная суммарная агрессивность.
В каждой из следующих $$$n$$$ строк вводятся целые числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$0 \le a_i \le b_i \le 10^9, 1 \le c_i \le n$$$).
Выведите единственное число — наибольшее количество монстров, которое может быть одновременно у одного игрока.
2 6 2 4 1 2 4 2
2
4 10 3 4 2 3 5 3 1 1 1 2 7 3
3
В первом тестовом примере, взяв всех монстров, игрок будет иметь суммарную агрессивность равной $$$4+2 = 6$$$.
Во втором тестовом примере, взяв первого, второго и четвёртого монстров, мы получим суммарную агрессивность равной $$$4 + 3 + 2=9$$$. Обратите внимание, что мы не можем взять всех четырёх монстров одновременно — тогда их суммарная агрессивность будет равна $$$4+5+1+7=18$$$, что превосходит $$$10$$$.
| ВКОШП.Junior - 2022. Финал |
|---|
| Закончено |
