金银岛
题目描述
某天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位。
样例输入
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
样例解释
第一组测试数据： 口袋承重上限为50，金属种类为4种，各金属的总重量和总价值依次为：第一种金属总重量10、总价值100，第二种金属总重量50、总价值30，第三种金属总重量7、总价值34，第四种金属总重量87、总价值100。 最终选取的金属及对应重量、价值如下：
- 选取第三种金属的全部7重量，价值34；
- 选取第一种金属的全部10重量，价值100；
- 选取第四种金属的33重量（该金属总重量87），对应价值为100×(33/87)≈37.93； 上述选取的金属总重量为7+10+33=50，恰好达到口袋承重上限，总价值为34+100+37.93=171.93，这是能带走的最大价值。
第二组测试数据： 口袋承重上限为10000，金属种类为5种，各金属的总重量和总价值依次为：第一种金属总重量1、总价值43，第二种金属总重量43、总价值323，第三种金属总重量35、总价值45，第四种金属总重量43、总价值54，第五种金属总重量87、总价值43。 最终选取的金属及对应重量、价值如下：
- 选取第一种金属的全部1重量，价值43；
- 选取第二种金属的全部43重量，价值323；
- 选取第三种金属的全部35重量，价值45；
- 选取第四种金属的全部43重量，价值54；
- 选取第五种金属的全部87重量，价值43； 上述选取的金属总重量为1+43+35+43+87=209，远小于口袋承重上限10000，总价值为43+323+45+54+43=508.00，这是能带走的最大价值（所有金属总价值仅为508，无法超过该值）。
