Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача B. Блокирующий пакет

Задачу добавил: alef

Успешно сдано решений: 5

Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт

Падение курса акций не было неожиданностью для Стива. Некоторое время назад компания 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

Сдать задачу

Задать вопрос жюри по этой задаче