Description

One day, KID flew to a gold and silver island using his aircraft. The island was abundant with precious metals. Although KID preferred gemstone artworks, he couldn't resist such valuable metals. However, he only carried a single bag that could hold items with a maximum weight of w. The island had s types of metals, each with different weights, denoted as n₁, n₂, ..., nₛ, and each type also had different total values, denoted as v₁, v₂, ..., vₛ. KID wanted to take away as much value as possible in one trip. What is the maximum value of metals he can carry? Note that the metals can be divided arbitrarily, and their value is proportional to their weight.

Input Format

The first line contains the number of test cases k, followed by k test cases. Each test case consists of 3 lines:

• The first line is a positive integer w (1 ≤ w ≤ 10000), representing the maximum weight the bag can carry.
• The second line is a positive integer s (1 ≤ s ≤ 100), representing the number of metal types.
• The third line contains 2s positive integers: n₁, v₁, n₂, v₂, ..., nₛ, vₛ, representing the total weight and total value of the first, second, ..., s-th metal type (1 ≤ nᵢ ≤ 10000, 1 ≤ vᵢ ≤ 10000).

Output Format

Output k lines, each corresponding to an input test case. The output should be accurate to 2 decimal places.

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