Candy

Interview

Time limit1sMemory limit256 MB

Summary

Pack J candies using the fewest boxes by filling the largest capacity boxes first.

Level: Easy3 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

You own a candy factory. Every day you pack $J$ candies into boxes and send them to the store.

The factory has $N$ boxes, and their sizes can differ. You want to use as few boxes as possible. A box does not have to be filled completely, so a partly filled box is fine.

Read the number of candies and the size of every box, then print the smallest number of boxes that holds all of the candies. The boxes are guaranteed to have enough room for all of the candies.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 10$ ). Each test case has the form below.

The first line of a test case contains the number of candies $J$ and the number of boxes $N$ ( $1 \le J, N \le 1000$ ).

Each of the next $N$ lines contains the height $R_i$ and the width $C_i$ of the $i$ -th box ( $1 \le R_i, C_i \le 10000$ ). Two boxes may have the same size. One box holds at most $R_i \times C_i$ candies.

Output

Print $T$ lines. On each line print the smallest number of boxes needed for the $i$ -th test case.

Examples4

Example 1
Input
```
1
20 5
3 4
2 5
1 8
3 3
2 5
```
Expected output
```
2
```

Example 2

Input

Expected output

1
2

Example 3
Input
```
1
1 1
1 1
```
Expected output
```
1
```
Example 4
Input
```
1
10 5
2 2
2 2
2 2
2 2
2 2
```
Expected output
```
3
```