29594번 - Резиновый рюкзак 스페셜 저지다국어

문제

Турист Геннадий готовится к очередному походу. Его старый, видавший виды рюкзак уже износился, да и вещей в него помещается не так уж много. Не стоит и говорить о том, что все возможные задачи об этом рюкзаке он уже прорешал.

Новый рюкзак Геннадия сделан из сверхпрочной резины. Если резину не растягивать, то в этот рюкзак можно положить предметов суммарным объемом не более $V_0$ кубических сантиметров. Однако, в этот рюкзак можно положить, запихать или в крайнем случае утрамбовать и больше предметов. Проблема в том, что если суммарный объем предметов будет равен $V > V_0,ドル то на все эти предметы будет действовать давление $P = V - V_0$.

Среди различных предметов, которые Геннадий хочет взять в поход, есть прочные, а есть и хрупкие. Например, внешняя клавиатура для ноутбука Геннадия не сможет вынести того же, что выдерживала проверенная годами палатка. Однако, даже хрупкие предметы, как показывает практика, могут быть ценными в походе. Поэтому Геннадий для каждого предмета, помимо занимаемого им объема $v_i,ドル определил его стоимость $c_i$ как меру того, насколько он хочет взять его в поход, а также вычислил максимальное давление $p_i,ドル которое он может выдержать.

Таким образом, перед Геннадием встала непростая задача --- как выбрать предметы таким образом, чтобы они, находясь все вместе в рюкзаке, смогли выдержать образующееся давление, и при этом стоимость получившегося набора была максимальна?

Геннадий --- турист бывалый, поэтому написанная им программа менее, чем за полсекунды справилась с этой задачей. А вы сможете повторить его достижение?

입력

В первой строке входного файла находятся два целых числа $N$ (1ドル \le N \le 100$) и $V_0$ (0ドル \le V_0 \le 10^9$) --- число предметов и начальный объем рюкзака.

Следующие $N$ строк содержат тройки целых чисел $v_i,ドル $c_i$ и $p_i$ --- объем, стоимость и максимальное давление, выдерживаемое $i$-тым предметом. 1ドル \le v_i \le 1000,ドル 0ドル \le c_i \le 10^6,ドル 0ドル \le p_i \le 10^9$.

출력

В первой строке выходного файла выведите число предметов $K,ドル которые необходимо взять, и максимальную достигнутую стоимость.

Во второй строке выведите $K$ чисел --- номера предметов, которые необходимо взять. Предметы нумеруются, начиная с единицы, в том порядке, в котором они даны во входном файле.

Если существует несколько вариантов ответа, выведите один из них.

제한

힌트