1797年金银岛（贪心算法（4.6））

1797:金银岛

总时间限制: 3000ms 内存限制: 65536kB
描述
某日，KID驾驶飞行器抵达了一个富含金银的岛屿，岛上遍布着大量珍贵金属。虽然KID更偏爱各类宝石艺术品，但面对如此宝贵的金属资源也难以拒绝。然而他仅携带了一个口袋，该口袋最多只能容纳重量为w的物品。岛上的金属共有s种类型，每种类型的金属重量各不相同，分别为n1, n2, … , ns，同时每种类型的总价值也存在差异，分别为v1, v2, … , vs。KID希望一次性带走尽可能多价值的金属，请问他最多能够带走多少价值的金属？需要注意的是，这些金属可以被任意分割，并且其价值与重量呈正比例关系。

输入
第1行给出测试数据的组数k，随后依次输入k组数据。

每组测试数据包含3行内容：第1行是一个正整数w（1 <= w <= 10000），表示口袋的最大承重能力；第2行是一个正整数s（1 <= s <= 100），表示金属种类的数量；第3行包含2s个正整数，依次为n1, v1, n2, v2, … , ns, vs，分别对应第一种、第二种、…、第s种金属的总重量和总价值（其中1 <= ni <= 10000，且1 <= vi <= 10000）。

输出
共输出k行内容，每行对应一组输入数据的结果。输出结果需保留小数点后两位。

样例输入
2
50
4