题目描述

可可岛位于距哥斯达黎加海岸 $300$ 英里的海中, 曾是 $17$ 世纪海盗的休息站, 海盗们将掠夺的财宝在此装装卸卸, 埋埋藏藏, 为这个无名小岛平添了神秘色彩,

据说岛上至少埋有 $6$ 处宝藏。某天小博历经千难万险到了可可岛上, 上面有许多珍贵的金属, 小博虽然更喜欢各种宝石的艺术品, 可是也不拒绝这样珍贵的金属。但是他只带着一个口袋, 口袋至多只能装重量为 $w$ 的物品。岛上金属有 $s$ 个种类, 每种金属重量不同, 分别为 $n_1,n_2,n_3,...,n_s$ 同时每个种类的金属总的价值也不同, 分别为 $v_1,v_2,v_3,...,v_s$

小博想一次带走价值尽可能多的金属, 问他最多能带走价值多少的金属。注意金属是可以被任意分割的, 并且金属的价值和其重量成正比。

输入格式

第一行是正整数 $T$ ，表示测试数据的组数。

接下来每组测试数据占三行。

第一行是一个正整数 $w$ 表示口袋承重上限。

第二行是一个正整数 $s$ 表示金属种类。

第三行有 $2s$ 个正整数, 分别为 $n_1,v_1,n_2,v_2,n_3,v_3,...,n_s,v_s$ ，其中$n_i,v_i(1\le i\le s)$ 分别表示第 $i$ 个金属的总重量和总价值

输出格式

输出共 $T$ 行, 每行输出对应一组输入数据。输出应精确到小数点后 $2$ 位。

样例1

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

数据范围

保证所有数据满足，$1\le w\le 10000,1\le s\le 100,1\le n_i,v_i\le 10000,1\le i\le s$