- Time limit:
- 1000 ms
- Memory limit:
- 256 MB

You are an owner of a candy factory. In each day, you have to pack J jelly beans into boxes for transfer to the stores.

You have some boxes which may be different in dimension. For your convenience, you want to use least boxes as possible. (You do not need to fill up the box, partly fill is acceptable.)

Write a program that get a number of jelly beans you receive from the factory and dimension of each box and find the number of least boxes can be used. We guarantee that there will be sufficient spaces for the jelly beans.

## Input

First line has a number T (1 ≤ T ≤ 10) represent number of test cases. Each test case has a format as follow.

First line has two numbers, J and N (1 ≤ J, N ≤ 1,000) represent number of jelly beans you receive from the factory and number of boxes you have.

For next N lines, each line has two numbers R_{i} and C_{i} (1 ≤ R_{i}, C_{i} ≤ 10,000) represent dimension (number of rows and columns) of i-th box (There can be two boxes with the same dimension.) This box can be packed with no more than R_{i} * C_{i} jelly beans.

## Output

Your output should have T lines. Each line represent the number of least boxes can be used in i-th test case.

**Editor: **

**Source: **
ACM ICPC 2015 Thailand Local Central Group B