Jelly Bean (acm15_jellybean)


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 Ri and Ci (1 ≤ Ri, Ci ≤ 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 Ri * Ci 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

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None