Задача F. День рождения ≡

Условие

У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. Какая удача — можно купить групповой билет сразу на всех, всего за S рублей!

Конечно, скидываться придется всем поровну. То есть, если Коля позовет k своих друзей, то каждому придется заплатить S / (k + 1) рублей (да, сам Коля тоже должен внести свою долю). При этом S не обязательно должно делиться на k + 1: главное — купить билет, а между собой друзья уж как-нибудь договорятся.

Всего у Коли n друзей, при этом i-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше b_i (больше денег у него просто с собой нет) и не меньше a_i (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).

Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число f_i — количество веселья, который тот произведет, если его позвать.

Помогите Коле выбрать подмножество друзей, которых Коля должен позвать с собой, чтобы максимизировать суммарное веселье.

Формат входного файла

В первой строке входного файлы содержится два целых числа: n и S (1 ≤ n ≤ 100 000, 0 ≤ S ≤ 10⁹) — количество друзей Коли и стоимость билета. В следующих n строках содержится по три целых числа: в i-й из этих строк находятся числа a_i, b_i и f_i (0 ≤ a_i ≤ b_i ≤ S, 0 ≤ f_i ≤ 10⁹). Они означают, что i-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между a_i и b_i, и он произведет f_i веселья.

Формат выходного файла

В первой строке выходного файла выведите два числа: k (количество приглашенных на вечеринку друзей) и F (максимальное суммарное веселье, которое можно получить). Во второй строке выведите k чисел — номера друзей, которых нужно пригласить.

Примеры тестов

4 10
4 5 40
2 4 30
2 6 10
3 5 20

2 50
2 4