eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

NP задача о рюкзаке

NP задача о рюкзаке

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

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

Первая строка содержит натуральные числа n (1n20) и w (1w10^9). Далее идут n строк по два числа: вес i-го предмета w[i] и его полезность p[i] (1w[i], p[i]10^9).

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

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

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

Пример

Входные данные #1
2 10
10 100
9 80
Выходные данные #1
1 100
1