说明

金银岛上有s种金属,每种金属重量不同，分别为$n_{1}$ , $n_{2}$.., $n_{s}$，同时每种金属的价值也不同，分别为$v_{1}$ ,$v_{2}$ .., $v_{s}$。一次带走的金属重量总和不能超过w，问最多能带走价值多少的金属？ 注意：金属是可以被任意分割的，金属的价值和重量成正比。

输入格式

第1行是测试数据的组数k，后面跟着k组输入。 每组测试数据占3行，第1行是一个正整数w(1<w≤10000)，表示口袋承重上限。第2行是一个正整数s(1<s<100)，表示金属种类。第3行有2s个正整数，分别为$n_{1}$,$v_{1}$,$n_{2}$,$v_{2}$,...,$n_{s}$,$v_{s}$,分别为第一种，第二种，…第s种金属的总重量和总价值(1≤$n_{i}$≤10000,1≤$v_{i}$≤10000)。

输出格式

k行，每行输出对应一个输入。输出应精确到小数点后2位。

样例

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