URI Online Judge | 1755

The Change

By Victor Marcilio Peixoto, UNIVASF BR Brazil

Timelimit: 2

Jõaozinho's father asked him to shop for a certain ingredient and gave him the following instructions:

1 - You may choose any brand as long as you buy as many units as possible.

2 - Don't come back empty-handed (buy at least one product).

3 - Don't bring me products from different brands.

4 - If you respect the first 3 constraints the change is yours.

Joãozinho is not that good in math and asked you to help him choose the brand that would maximize the change, respecting the constraints. You don't like lazy people and promissed Joãozinho that you would build him a program to solve part of his problem: finding the best change (without mentioning which brand would lead to such change).


The first line of input contains an integer T (1 ≤ T ≤ 2000), the number of test cases.

Each test case has 2 lines. The first line has the integeres D (10 ≤ D ≤ 500) and N ( 2 ≤ N ≤ 300), indicating the amount of money Joãozinho took to the market and the number of different brands available (you may assume that the store has enough stock to supply any demand), respectively.

The second line contains N floating-point numbers pi, representing the cost of one unit manufactured by brand bi. You may assume that the any price will have at most 2 digits after the decimal point.


For each test case print a single line containing a floating-point number with 2 digits after the decimal point: The largest change that Joãozinho can earn.

Input Sample Output Sample

50 3
15 50 24.35
50 4
15 16.50 50 22.40