| Сириус.2019.Ноябрь.Очный отбор |
|---|
| Finished |
У Арсения есть $$$n$$$ зверьков. Каждый из них обладает характером, поэтому, если в клетке, где находится $$$i$$$-й зверек, есть не больше $$$c_i$$$ зверьков, то его агрессивность будет $$$a_i$$$, а если больше, то его агрессивность будет $$$b_i$$$ ($$$a_i \le b_i$$$).
Также у Арсения есть клетка прочностью $$$s$$$, которая выдержит зверьков, суммарная агрессивность которых не больше $$$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
