题目描述

某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属。他带着一个最多能装重量为 $w$ 物品的口袋。岛上有 $s$ 种金属，每种金属的总重量为 $n_i$，总价值为 $v_i$。KID想带走价值尽可能多的金属，问最多能带走多少价值的金属。注意金属可以被任意分割，且价值与重量成正比。

输入格式

第1行是测试数据的组数 $k$，后面跟着 $k$ 组输入。

每组测试数据占3行：

• 第1行：口袋承重上限 $w$ ($1 \leq w \leq 10000$)
• 第2行：金属种类数 $s$ ($1 \leq s \leq 100$)
• 第3行：$2s$ 个正整数，分别为 $n_1, v_1, n_2, v_2, ..., n_s, v_s$ ($1 \leq n_i \leq 10000$, $1 \leq v_i \leq 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