【題目描述】

金銀島上有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