시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB11119.091%

문제

У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача --- можно купить групповой билет сразу на всех, всего за $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$ чисел --- номера друзей, которых нужно пригласить.

예제 입력 1

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

예제 출력 1

2 50
2 4