Лут с ограничением по весу

В игре ты идёшь в рейд с маленьким рюкзаком. На земле лежат предметы: у каждого есть вес и ценность. Рюкзак выдержит не больше заданного веса.

Твоя цель — унести набор предметов так, чтобы суммарная ценность была максимальной, а суммарный вес не превышал ограничение.

Важно: ответ может не помещаться в 32-битный тип (как на олимпиадах). В Python это не проблема.

Формат ввода

В первой строке даны два целых числа n и C — количество предметов и максимальный допустимый вес рюкзака.

В следующих n строках записаны пары целых чисел w_i и v_i — вес и ценность i-го предмета.

Формат вывода

Выведите одно целое число — максимальную суммарную ценность, которую можно унести.

Ограничения

• 1 ≤ n ≤ 18
• 0 ≤ C ≤ 18000
• 1 ≤ w_i ≤ 1000
• 0 ≤ v_i ≤ 1000

Пример

Ввод

4 7
3 10
4 11
5 13
2 5

Вывод

21

(Можно взять предметы с весами 3 и 4: общий вес 7, ценность 21.)

Ключевое наблюдение: предметов очень мало (n ≤ 18), значит количество всех наборов равно 2^n, это всего до 262144. Такой перебор проходит быстро, и не нужен «тяжёлый» динамический рюкзак.

Приём: битмаска. Число mask от 0 до 2^n - 1 кодирует подмножество: i-й бит равен 1, если предмет i взят. Для каждого mask считаем суммарный вес и ценность, и обновляем ответ, если вес не превышает C.

План:

• Считать n, C, массивы w[i], v[i].
• Завести best = 0.
• Для всех mask в диапазоне 0 .. (1<<n)-1:
• total_w = 0, total_v = 0.
• Пройти по i = 0..n-1; если предмет выбран (mask >> i & 1), прибавить w[i] и v[i].
• Если в процессе total_w > C, можно сразу прекратить просмотр этого mask (раннее отсечение).
• Иначе обновить best = max(best, total_v).
• Вывести best.

Сложность: O(n * 2^n), здесь это примерно 18 * 262144 операций — нормально.

Частая ошибка: забыть про раннее отсечение и/или неправильно обработать «прерывание» — важно не обновлять ответ для маски, которая уже превысила C.