You are given a sack which can hold grain of weight w. You have grains of n different varieties, each weighing weighti kg and having a value of ₹ moneyi. What is the maximum worth of grain the sack can be filled with?

Example:

w: 12
n: 4
Grains (weight, value): [(5, 20), (8, 20), (4, 15), (5, 8)]
Output: 42.50
Explanation: Take 5 kg of 1st grain, 3 kg of 2nd grain and 4 kg of 3rd grain.

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input contains the following lines:

• The first line contains two space-separated integers w and n denoting sack weight capacity and number of different grains respectively.
• The next n lines, each have two space-separated integers- weight_i and value_i denoting the weight and value of each type of grain.

Output Format

One line for each test case, with the maximum worth of grain that can be filled in the sack (accurate upto 2 decimal places).

Sample Input

2
12 4
5 20
8 20
4 15
5 8
10 3
4 8
2 5
3 8

Expected Output

42.50
21.00

Constraints

1 <= t <= 10
1 <= w <= 109
1 <= n <= 5*104
1 <= weighti, valuei <= 104