Description

On Treasure Island, there are $s$ types of metals, each with different weights ($n_1$, $n_2$, ..., $n_s$) and different values ($v_1$, $v_2$, ..., $v_s$). The total weight of metals that can be carried at once cannot exceed $w$. What is the maximum value of metals that can be carried?
Note: Metals can be divided into any fraction, and the value of a metal is proportional to its weight.

Input Format

The first line contains the number of test cases $k$, followed by $k$ groups of input.
Each test case consists of 3 lines: Line 1 contains a positive integer $w$ ($1 < w ≤ 10000$), representing the maximum weight capacity. Line 2 contains a positive integer $s$ ($1 < s < 100$), representing the number of metal types. Line 3 contains $2s$ positive integers: $n_1$, $v_1$, $n_2$, $v_2$, ..., $n_s$, $v_s$, representing the total weight and total value of the first, second, ..., $s$-th type of metal ($1 ≤ n_i ≤ 10000$, $1 ≤ v_i ≤ 10000$).

Output Format

$k$ lines, each containing the result for one test case. The output should be accurate to 2 decimal places.

Sample

2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

171.93
508.00