Задача B. Блокирующий пакет
Задачу добавил: alef
Успешно сдано решений: 6
Падение курса акций не было неожиданностью для Стива. Некоторое время назад компания Quantum Artificial Intelligence заявила о желании выйти на рынок программного обеспечения для небольших устройств. Эта компания когда-то планировала развивать разработки, связанные с искусственным интеллектом, но не снискала успехов на этом поприще, закрепившись в итоге на рынке программного обеспечения для промышленных роботов. И теперь целью компании стало заполучить блокирующий пакет акций Gadget Operating System.
Менеджеры компании Quantum Artificial Intelligence определили, что блокирующим будет пакет из s акций. Они планируют обратиться с предложением о продаже акций к n акционерам Gadget Operating System.
Для каждого акционера #i известно количество акций ai, которым он владеет. Кроме того, акционер #i согласится продать свои акции только в том случае, если у покупателя будет к моменту покупки не менее bi акций.
Менеджеры компании Quantum Artificial Intelligence хотят как можно быстрее приобрести желаемое ими количество акций. Однако по ряду причин они могут заключать не более одной сделки в день. Ваша задача — определить, какое минимальное количество дней потребуется менеджерам, чтобы приобрести желаемое (или большее) количество акций.
В первой строке содержится целое число s (1 ≤ s ≤ 109) — количество акций, которое хотят приобрести менеджеры.
Во второй строке содержится целое число n (1 ≤ n ≤ 105) — количество акционеров, у которых менеджеры могут приобрести акции.
В каждой из следующих n строк содержится по два целых числа ai и bi (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) через пробел.
В первой строке выведите число q — минимальное количество дней, спустя которое менеджеры могут стать обладателями желаемого ими количества акций. Если им это не удастся, выведите в качестве ответа - 1.
Во второй строке выведите q чисел — номера акционеров в том порядке, в котором менеджеры приобретали у них акции. Считайте, что акционеры занумерованы в порядке их упоминания во входных данных. Если существует несколько вариантов ответа — выведите любой.
28
8
5 2
7 25
4 0
6 1
2 20
3 3
8 7
4 15
6
3 4 1 6 7 8
5
1
5 1
-1