3994번 - Exact Measurement 스페셜 저지다국어

문제

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 q_i 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¹⁸, 1 ≤ n ≤ 10⁵). The next n lines contain pairs of numbers k_i and q_i (0 ≤ k_i ≤ 18, 1 ≤ q_i · 10^k_i ≤ 10¹⁸).

출력

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.

제한

힌트