Задача №3561. День рождения
У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за \(S\) рублей!
Конечно, скидываться придется всем поровну. То есть, если Коля позовет \(k\) своих друзей, то каждому придется заплатить \(S/(k + 1)\) рублей (да, сам Коля тоже должен внести свою долю). При этом \(S\) не обязательно должно делиться на \(k + 1\): главное — купить билет, а между собой друзья уж как-нибудь договорятся.
Всего у Коли \(n\) друзей, при этом \(i\)-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше \(b_i\) (больше денег у него просто с собой нет) и не меньше \(a_i\) (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).
Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число \(f_i\) — количество веселья, который тот произведет, если его позвать.
Помогите Коле выбрать подмножество друзей, которых Коля должен позвать с собой, чтобы максимизировать суммарное веселье.
В первой строке входного файлы содержится два целых числа: \(n\) и \(S\) (\(1 \le n \le 100\,000\), \(0 \le S \le 10^9\)) — количество друзей Коли и стоимость билета. В следующих \(n\) строках содержится по три целых числа: в \(i\)-й из этих строк находятся числа \(a_i\), \(b_i\) и \(f_i\) (\(0 \le a_i \le b_i \le S\), \(0 \le f_i \le 10^9\)). Они означают, что \(i\)-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между \(a_i\) и \(b_i\), и он произведет \(f_i\) веселья.
В первой строке выходного файла выведите два числа: \(k\) (количество приглашенных на вечеринку друзей) и \(F\) (максимальное суммарное веселье, которое можно получить). Во второй строке выведите \(k\) чисел — номера друзей, которых нужно пригласить.