Рюкзак для пика Ленина
Пик Ленина (7134 м) на границе Кыргызстана и Таджикистана — один из самых популярных семитысячников мира. Базовый лагерь экспедиций стоит на поляне Ачик-Таш на Памире, куда альпинисты добираются из Оша по Памирскому тракту.

Пик Ленина, вид со стороны села Сары-Могол. Фото: Nihongarden, CC BY-SA 3.0, Wikimedia Commons
Альпинист Эмиль собирает рюкзак для штурма вершины. На выбор у него n предметов снаряжения; предмет i весит w[i] граммов и имеет полезность v[i] (опытные гиды оценили, насколько он повышает шансы на успех). Рюкзак выдержит не более W граммов, а чтобы штурм разрешили, суммарная полезность взятых предметов должна быть не меньше V.
Эмиль хочет знать, сколько у него вариантов. Найдите количество подмножеств предметов (в том числе пустое), у которых суммарный вес не больше W, а суммарная полезность не меньше V.
Входные данные
В первой строке — три целых числа n, W, V (1 ≤ n ≤ 40, 0 ≤ W, V ≤ 4 · 10¹⁶).
В каждой из следующих n строк — два целых числа w[i] и v[i] (1 ≤ w[i] ≤ 10¹⁵, 0 ≤ v[i] ≤ 10¹⁵).
Выходные данные
Выведите одно целое число — количество подходящих подмножеств.
Пример 1
Вход:
4 10 7
5 4
4 3
3 3
6 5
Выход:
4
Пояснение
Подходят наборы {1, 2} (вес 9, полезность 7), {1, 3} (8 и 7), {2, 4} (10 и 8) и {3, 4} (9 и 8).
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 20 | n ≤ 16 |
| 2 | 25 | V = 0 и все v[i] = 0 |
| 3 | 55 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Примечание
Ответ может достигать 2⁴⁰ — используйте 64-битные целые числа.
Комментарии