G. Нужно больше золота
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Начался новый семестр — а значит и ваши тренировки в киберспортивной сборной по Doka 3.

Сегодня вы впервые играете на герое по имени Мидас. Опытные сокомандники рассказали, что сила данного героя напрямую зависит от количества накопленного им золота.

Чтобы получать золото, вы должны побеждать монстров.

На карте мира расположено n монстров, с которыми вы можете сражаться в любом порядке. С каждым монстром можно сразиться только один раз.

Для i-го монстра известны две характеристики:

  • gi — сколько золота вы получите после победы над монстром;
  • bi — какой запас золота вам необходим, чтобы победить монстра. Золото при этом не тратится.

Изначально у вас 0 золота. Ваша цель на игру — накопить не менее w золота.

Найдите минимальное количество монстров, которых вам необходимо победить для достижения цели, а также номера монстров в порядке сражений с ними.

Входные данные

В первой строке содержится целое число w (1 ≤ w ≤ 109) — количество золота, являющееся вашей целью на игру.

Во второй строке содержится целое число n (1 ≤ n ≤ 105) — количество монстров, с которыми вы можете сразиться.

В каждой из следующих n строк содержится по два целых числа gi и bi (1 ≤ gi ≤ 109,  0 ≤ bi ≤ 109) — характеристики i-го монстра из условия задачи.

Выходные данные

В первой строке выведите целое число k — минимальное количество сражений с монстрами, необходимое для достижения цели в w золота. Если вы никак не можете достичь цели — выведите  - 1.

В случае успеха во второй строке выведите k чисел — номера монстров в том порядке, в котором вы должны сражаться с ними.

Считайте, что монстры занумерованы в порядке их упоминания во входных данных.

Если существует несколько вариантов ответа, приводящих к минимальному количеству сражений — выведите любой.

Примеры
Входные данные
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
Примечание

Первый тестовый пример

Опишем последовательность сражений и заработанного золота.

  • Вначале у вас 0 золота, поэтому вы можете сразиться только с 3-м монстром и получить 4 золота.
  • Далее вы сражаетесь с 4-м монстром и получаете 6 золота — всего у вас 10 золота.
  • После этого вы сражаетесь с 1-м монстром и получаете дополнительные 5 золота — всего 15.
  • Затем вы сражаетесь с 6-м монстром и получаете дополнительные 3 золота — всего 18 золота.
  • Последние две битвы вы проводите с монстрами 7 и 8 (в любом порядке, так как вам хватает золота) — суммарно вы получаете 12 золота, что суммарно даёт 30.
  • Вам необходимо 28 золота, значит цель достигнута.

Обратите внимание, что существуют и другие порядки / выборы монстров для сражений.

Второй тестовый пример

У вас 0 золота в начале, а единственный доступный монстр требует 1 золота для победы.

Вы не можете набрать w = 5 золота, значит необходимо вывести  - 1.