Treasure Island

Background

Special for beginners, ^_^

Problem Description

One day KID flew a flying machine to a gold-and-silver island where many precious metals lay. Although KID prefers artworks made of gems, he does not refuse such precious metals. However, he only brought one bag, and the bag can hold items of total weight at most $w$.

There are $s$ kinds of metals on the island. The metals of different kinds have different weights, namely $n_1, n_2, \dots, n_s$, and the total value of each kind is also different, namely $v_1, v_2, \dots, v_s$. KID wants to take away as much value of metals as possible in one trip. What is the maximum total value he can take?

Note that the metals can be divided arbitrarily, and the value of a metal is proportional to its weight.

Input Format

The first line is the number of test cases $k$, followed by $k$ groups of input.

Each test case occupies $3$ lines.

The first line is a positive integer $w$ ($1 \le w \le 10000$), the weight limit of the bag.

The second line is a positive integer $s$ ($1 \le s \le 100$), the number of kinds of metal.

The third line contains $2s$ positive integers, namely $n_1, v_1, n_2, v_2, \dots, n_s, v_s$, which are the total weight and total value of the first, second, ..., $s$-th kind of metal ($1 \le n_i \le 10000$, $1 \le v_i \le 10000$).

Output Format

Output $k$ lines, each line corresponding to one input. The output should be accurate to $2$ decimal places.

Sample Input 1

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

Sample Output 1

171.93
508.00

Constraints

1s, 1024KiB for each test case.