P1183 - 金银岛
题目描述
某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为$w$的物品。岛上金属有$s$个种类, 每种金属重量不同，分别为$n_1$, $n_2$, ... , $n_s$，同时每个种类的金属总的价值也不同，分别为$v_1$,$v_2$, ..., $v_s$。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。
输入格式
第1行是测试数据的组数$k$ ($1 <= k <= 100$)，后面跟着$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位。
输入输出样例 #1
输入 #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
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：P1183.in，输出文件名为：P1183.out