|
Щедрое приданое
(Время: 1 сек. Память: 16 Мб Сложность: 77%)
Дочь короля Флатландии выходит замуж за прекрасного принца. Король хочет приготовить к их свадьбе щедрое приданое, но он не уверен, какие драгоценные камни из своей коллекции преподнести.
В коллекции короля N драгоценных камней, про каждый камень известен его вес Wi и его ценность Vi. Король хотел бы преподнести как можно более ценное приданое, но с другой стороны он хочет, чтобы суммарный вес камней был разумным. Вес считается разумным, если он находится между L и R (включительно).
Помогите королю выбрать камни для приданого, чтобы их вес был разумным, а суммарная их ценность была максимальна.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа N, L и R (1 ≤ N ≤ 32, 0 ≤ L ≤ R ≤ 1018). Следующие N строк описывают драгоценные камни, каждая строка содержит два целых числа: Wi и Vi (1 ≤ Wi, Vi ≤ 1015).
Выходные данные
Первая строка выходного файла OUTPUT.TXT должна содержать число K – количество камней, которое следует выбрать. Вторая строка должна содержать K чисел от 1 до N номера камней (камни нумеруются, начиная с 1, в том порядке, в котором они заданы во входном файле). Если существует несколько решений, выведите любое. Если выбрать искомое приданое невозможно, выведите K = 0.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 6 8
3 10
7 3
8 2 | 1
2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
