Дочь короля Флатландии собирается выйти за прекрасного принца.
Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать.
В коллекции принца n бриллиантов, каждый характеризуется весом w
i и стоимостью v
i.
Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L.
Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L, R].
Входные данные:
Первая строка содержит число n (1 <= n <= 32), L и R (0 <= L <= R <= 10
18).
Следующие n строк описывают бриллианты и содержат по два числа - вес и стоимость соответствующего бриллианта (1 <= wi, vi <= 10
15).
Выходные данные:
Первая строка вывода должна содержать k - количество бриллиантов, которые нужно подарить принцессе.
Вторая строка должна содержать номера даримых бриллиантов.
Бриллианты нумеруются от 1 до n в порядке появление во входных данных.
Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода.
Примеры:
| Входные данные |
Выходные данные |
3 6 8
3 10
7 3
8 2 |
1
2 |