G. Need More Gold
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A new semester has begun — which means your training in the esports team for Doka 3.

Today you are playing for the first time as a hero named Midas. Experienced teammates have told you that the power of this hero directly depends on the amount of gold he accumulates.

To earn gold, you must defeat monsters.

On the world map, there are n monsters that you can fight in any order. You can fight each monster only once.

For the i-th monster, two characteristics are known:

  • gi — how much gold you will receive after defeating the monster;
  • bi — how much gold reserve you need to defeat the monster. The gold is not spent in this process.

Initially, you have 0 gold. Your goal in the game is to accumulate at least w gold.

Find the minimum number of monsters you need to defeat to achieve this goal, as well as the indices of the monsters in the order you should fight them.

Input

The first line contains an integer w (1 ≤ w ≤ 109) — the amount of gold that is your goal in the game.

The second line contains an integer n (1 ≤ n ≤ 105) — the number of monsters you can fight.

Each of the following n lines contains two integers gi and bi (1 ≤ gi ≤ 109,  0 ≤ bi ≤ 109) — the characteristics of the i-th monster as described in the problem.

Output

In the first line, output an integer k — the minimum number of battles with monsters required to achieve the goal of w gold.

If you cannot achieve the goal in any way — output  - 1.

If successful, in the second line output k numbers — the indices of the monsters in the order you should fight them.

Assume that the monsters are numbered in the order they are mentioned in the input data.

If there are multiple valid answers that lead to the minimum number of battles, output any of them.

Examples
Input
28
8
5 2
7 25
4 0
6 1
2 20
3 3
8 7
4 15
Output
6
3 4 1 6 7 8
Input
5
1
5 1
Output
-1
Note

First test example

Let's describe the sequence of battles and the gold earned.

  • At the beginning, you have 0 gold, so you can only fight the 3-rd monster and earn 4 gold.
  • Next, you fight the 4-th monster and earn 6 gold — now you have 10 gold in total.
  • After that, you fight the 1-st monster and earn an additional 5 gold — now you have 15 in total.
  • Then you fight the 6-th monster and earn an additional 3 gold — now you have 18 gold in total.
  • The last two battles are with monsters 7 and 8 (in any order, as you have enough gold) — in total, you earn 12 gold, bringing your total to 30.
  • You need 28 gold, so the goal is achieved.

Note that there are other orders/choices of monsters for battles.

Second test example

You start with 0 gold, and the only available monster requires 1 gold to defeat.

You cannot accumulate w = 5 gold, so you must output  - 1.