정확한 계량

피터는 화학 실험실에서 일한다. 새 실험을 위해 그는 시약을 정확히 $x$ 나노그램(ng)만큼 계량해야 한다. 그에게는 양팔 저울과 여러 개의 표준 분동이 있다.

분동은 $n$개의 밀봉된 상자에 담겨 있다. $i$번째 상자에는 각각 무게가 $10^{k_i}$ ng인 동일한 분동이 $q_i$개 들어 있다. 상자에서 분동을 꺼내려면 상자를 열어야 하며, 연 상자에서는 그 안의 분동을 $0$개부터 $q_i$개까지 원하는 만큼 꺼낼 수 있다.

피터는 꺼낸 분동들의 무게 합이 정확히 $x$ ng이 되도록 하되, 여는 상자의 수를 최소로 하고 싶다. 열어야 하는 상자의 최소 개수를 구하여라.

첫째 줄에 두 정수 $x$와 $n$이 주어진다 ($1 \le x \le 10^{18}$, $1 \le n \le 10^5$).

다음 $n$개의 줄에는 각 상자를 나타내는 두 정수 $k_i$와 $q_i$가 주어진다 ($0 \le k_i \le 18$, $1 \le q_i \cdot 10^{k_i} \le 10^{18}$).

정확히 $x$ ng을 계량하기 위해 열어야 하는 상자의 최소 개수를 한 줄에 출력한다. 정확히 계량하는 것이 불가능하면 $-1$을 출력한다.