정확한 계량

시간 제한1초메모리 제한128 MB

요약

각 상자에는 무게 10^k_i인 추가 q_i개씩 들어 있을 때, 고른 추의 합이 정확히 x가 되도록 열어야 하는 상자의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 수학, 비트 연산
정답자: 아직 제출이 없습니다

문제

피터는 화학 실험실에서 일한다. 새 실험을 위해 그는 시약을 정확히 $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$ 을 출력한다.

예제3

예제 1
입력
```
289 4
2 3
1 5
1 8
0 30
```
예상 출력
```
3
```
예제 2
입력
```
300 4
2 3
1 5
1 7
0 30
```
예상 출력
```
1
```
예제 3
입력
```
201 1
2 3
```
예상 출력
```
-1
```