Рабочее место участника

Peter is working in a secret chemical laboratory. For his new experiment he needs to measure exactly `x` nanograms of a secret reagent. He has a balance and several standard masses, and his goal is to choose a set of standard masses with total sum equal to `x` ng.

Standard masses come in `n` sealed boxes. The `i`-th box contains qi identical masses of `10^{k_i}` ng. Peter wants to open the minimal number of boxes to take a set of masses with the sum of their weights of `x` ng.

The first line of the input file contains two integer numbers `x` and `n` (`1\ ≤\ x\ ≤\ 10^18`, `1\ ≤\ n\ ≤\ 10^5`). The next `n` lines contain pairs of numbers `k_i` and `q_i` (`0\ ≤\ k_i\ ≤\ 18`, `1\ ≤\ q_i\ *\ 10^{k_i}\ ≤\ 10^18`)

On the first line output the minimal number of boxes that should be opened. On the second line output the numbers of these boxes in any order. Boxes are numbered in the order they appear in the input file starting from 1. If it is impossible to measure exactly `x` ng, output a single line with `-1`.

289 4
2 3
1 5
1 8
0 30

3
1 3 4

300 4
2 3
1 5
1 7
0 30

1
1

201 1
2 3

-1