描述

某天，KID 利用飞行器来到了一座金银岛。岛上有许多珍贵的金属，虽然 KID 更喜欢宝石艺术品，但也不拒绝这些贵重的金属。

不过，KID 只带了一个口袋，最多只能装下重量为 $w$ 的物品。

岛上一共有 $s$ 种金属，第 $i$ 种金属的总重量为 $n_i$，总价值为 $v_i$。金属可以被任意分割，并且金属的价值与其重量成正比。

KID 希望在不超过口袋承重上限的前提下，带走总价值尽可能大的金属。

请你计算他最多能带走的金属总价值。

格式

输入

• 第一行包含一个整数 $k$，表示测试数据的组数。

• 接下来是 $k$ 组测试数据，每组测试数据包含三行：

  • 第一行一个正整数 $w$（$1 \le w \le 10000$），表示口袋的最大承重；
  • 第二行一个正整数 $s$（$1 \le s \le 100$），表示金属的种类数；
  • 第三行包含 $2s$ 个正整数：$$n_1, v_1, n_2, v_2, \dots, n_s, v_s$$ 分别表示每种金属的总重量和总价值 （$1 \le n_i, v_i \le 10000$）。

输出

• 输出 $k$ 行，每行输出对应一组测试数据的答案。
• 结果保留 小数点后 $2$ 位。

样例

输入1

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

输出1

171.93
508.00