Группа туристов собирается в водный поход. На лодочную базу прибыл арендованный грузовик, в который будут погружены байдарки и катамараны, а затем доставлены на место отправления. Известно, что все байдарки равны по размерам между собой (и занимают 1 куб. метр пространства), а катамараны равны по размерам между собой и в два раза больше байдарки (и занимают 2 куб. метра пространства).
Каждое плавсредство обладает некоторой грузоподъемностью, причем даже неотличимые с виду плавсредства могут обладать разной грузоподъемностью.
По заданному объему кузова грузовика и списку плавсредств (для каждого известен его тип и грузоподъемность) определите набор, который можно перевести и который обладает максимальной возможной грузоподъемностью. Объем кузова грузовика можно использовать максимально эффективно, то есть в кузов всегда можно погрузить плавсредство объемом не превышающее свободный объем кузова.
Выходные данные
В первую строку выведите искомую максимальную грузоподъемность набора. Во вторую строку выведите номера плавсредств, которые составляют оптимальный набор. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2
2 7
1 3
|
7
2
|