#452. 【85课】【3470】金银岛

【85课】【3470】金银岛

说明

金银岛上有s种金属,每种金属重量不同,分别为n1 , n2.., ns,同时每种金属的价值也不同,分别为v1 , v2 .., vs。一次带走的金属重量总和不能超过w,问最多能带走价值多少的金属?

注意:金属是可以被任意分割的,金属的价值和重量成正比。

输入格式

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

每组测试数据占33行,第11行是一个正整数w(1<w≤10000),表示口袋承重上限。第22行是一个正整数s(1<s<100),表示金属种类。第33行有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