说明

金银岛上有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)。

输出格式

样例

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