B. Грузовик
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

Группа туристов собирается в водный поход. На лодочную базу прибыл арендованный грузовик, в который будут погружены байдарки и катамараны, а затем доставлены на место отправления. Известно, что все байдарки равны по размерам между собой (и занимают 1 куб. метр пространства), а катамараны равны по размерам между собой и в два раза больше байдарки (и занимают 2 куб. метра пространства).

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

По заданному объему кузова грузовика и списку плавсредств (для каждого известен его тип и грузоподъемность) определите набор, который можно перевести и который обладает максимальной возможной грузоподъемностью. Объем кузова грузовика можно использовать максимально эффективно, то есть в кузов всегда можно погрузить плавсредство объемом не превышающее свободный объем кузова.

Входные данные

В первой строке записана пара целых чисел n и v (1 ≤ n ≤ 105; 1 ≤ v ≤ 109), где n это количество плавсредств на лодочной базе, а v — объем кузова грузовика в кубических метрах. Следующие n строк содержат описания плавсредств. Каждое описание это пара чисел ti, pi (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 104), где ti это тип плавсредства (1 — байдарка, 2 — катамаран), а pi его грузоподъемность. Плавсредства нумеруются с единицы в порядке их появления во входном файле.

Выходные данные

В первую строку выведите искомую максимальную грузоподъемность набора. Во вторую строку выведите номера плавсредств, которые составляют оптимальный набор. Если решений несколько, выведите любое.

Примеры
Входные данные
3 2
1 2
2 7
1 3
Выходные данные
7
2