Your friend works in a shipyard, and in his work he controls the containers that are being loaded from and on the ships. Your friend likes from time to time to remove some containers from the ship's manifest, and adjust the appropriate reports so that the container is left in the shipyard. In this way, he can later on sell what is in the container.

Tomorrow a ship with refrigerators will be unloaded, and your friend spots a chance to steal one container. However, he doesn't have the information about the money value of the contents of a container and no information about the precise contents of a container. At the moment when he can modify the manifest he only knows what is the weight of the container. Since stealing containers is very risky, your friend wants to choose the containers very carefully and only when his profit is worth the risk.

That's why he needs your help. He knows that each refrigerator's type is one of N possible types. For every type i he knows its market value v_i and also its weight w_i in kilograms. Once the container will appear in the shipyard he will also know the precise weight of W kilograms of all the things that are inside a container. He needs to act fast and the calculations are not that easy, so he asks you to write a program that will calculate what is the minimum possible total value of all the refrigerators in the container. He wants minimum, because he wants to consider the worst case scenario.

Input

The input consists of T <= 5 test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing one integer W that indicates the exact weight of the contents of a container. The total weight of the refrigerators will be at most 10000 kilograms. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various types of refrigerators. Following this there are exactly N lines, each specifying one refrigerator type. These lines contain two integers each, v_i and w_i (1 <= v_i <= 50000, 1 <= w_i <= 10000). v_i is the value of the refrigerator, and w_i is its weight in kilograms.

Output

Print exactly one line of output for each test case. The line must contain single number X, where X is the minimum possible total value of refrigerators whose weight sum to W. If the total weight of the refrigerators cannot be reached exactly, which means that somewhere your friend made a mistake in the data, then print -1.

Example

Input:
3
100
2
1 1
30 50
100
2
1 1
50 30
5
2
10 3
20 4

Output:
60
100
-1