【题目描述】

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

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

【输入】

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

每组测试数据占33行，第11行是一个正整数w𝑤(1<w≤100001<𝑤≤10000)，表示口袋承重上限。第22行是一个正整数s𝑠(1<s<1001<𝑠<100)，表示金属种类。第33行有2s2𝑠个正整数，分别为n1𝑛1,v1𝑣1,n2𝑛2,v2𝑣2,...,ns𝑛𝑠,vs𝑣𝑠,分别为第一种，第二种，…第s𝑠种金属的总重量和总价值(1≤ni≤100001≤𝑛𝑖≤10000,1≤vi≤100001≤𝑣𝑖≤10000)。

【输出】

k𝑘行，每行输出对应一个输入。输出应精确到小数点后22位。

【输入样例】

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