Одной из классических NP-полных задач является так называемая Задача о рюкзаке. Формулируется она следующим образом.

Дано n предметов, каждый из которых характеризуется весом wi и полезностью pi. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал w, а суммарная полезность была максимальной.

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

Первая строка содержит натуральные числа n (1 ≤ n ≤ 20) и w (1 ≤ w ≤ 109). Далее идут n строк по два числа: вес i-го предмета wi и его полезность pi (1 ≤ wi, pi ≤ 109).

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

В первой строке выведите количество выбранных предметов и их суммарную полезность. Во второй строке выведите их номера в возрастающем порядке (предметы нумеруются с единицы в порядке, в котором они заданы на входе).

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