사탕

면접 대비

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

요약

사탕 J개를 담기 위해 용량이 큰 상자부터 채워 필요한 최소 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

당신은 사탕 공장의 주인이다. 날마다 사탕 $J$ 개를 상자에 담아 가게로 보내야 한다.

공장에는 상자가 $N$ 개 있고, 크기는 서로 다를 수 있다. 상자는 되도록 적게 쓰려고 한다. 상자를 가득 채울 필요는 없고, 일부만 채워도 된다.

사탕의 개수와 각 상자의 크기를 입력받아, 사탕을 모두 담는 데 필요한 상자의 최소 개수를 출력하는 프로그램을 작성하라. 사탕을 모두 담을 공간은 충분하다고 보장한다.

입력

첫 줄에 테스트 케이스의 개수 $T$ ( $1 \le T \le 10$ )가 주어진다. 각 테스트 케이스는 아래 형식을 따른다.

테스트 케이스의 첫 줄에 사탕의 개수 $J$ 와 상자의 개수 $N$ 이 주어진다 ( $1 \le J, N \le 1000$ ).

다음 $N$ 개의 줄에는 줄마다 $i$ 번째 상자의 세로 길이 $R_i$ 와 가로 길이 $C_i$ 가 주어진다 ( $1 \le R_i, C_i \le 10000$ ). 두 상자의 크기가 같을 수도 있다. 한 상자에는 사탕을 $R_i \times C_i$ 개보다 많이 담을 수 없다.

출력

$T$ 개의 줄을 출력한다. 각 줄에 $i$ 번째 테스트 케이스에서 필요한 상자의 최소 개수를 출력한다.

예제4

예제 1
입력
```
1
20 5
3 4
2 5
1 8
3 3
2 5
```
예상 출력
```
2
```

예제 2

입력

예상 출력

1
2

예제 3
입력
```
1
1 1
1 1
```
예상 출력
```
1
```
예제 4
입력
```
1
10 5
2 2
2 2
2 2
2 2
2 2
```
예상 출력
```
3
```