无名岛的宝藏

题目描述

童童到了加勒比海一个无名岛上，上面有许多珍贵的金属。但是童童只带着一个袋子，至多只能装重量为 $w$ 的物品。岛上金属有 $s$ 个种类, 每种金属重量不同，分别为 $n_1,n_2,...,n_s$，同时每个种类的金属总的价值也不同，分别为 $v_1,v_2, ..., v_s$。童童想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。 **注意:金属是可以被任意分割的，并且金属的价值和其重量成正比。**

输入格式

第 $1$ 行是测试数据的组数 $k$，后面跟着 $k$ 组数据。 每组测试数据 $3$ 行,接下 $3$ 行 第 $1$ 行是一个正整数 $w$，表示口袋承重上限。 第 $2$ 行是一个正整数 $s$ ，表示金属种类。 第 $3$ 行有 $2×s$ 个正整数，分别为$n_1,v_1,n_2,v_2,...,n_s,v_s$分别为第一种，第二种，...，第 $s$ 种金属的总重量和总价值。

输出格式

$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

提示

#### 数据范围与提示 $1\le n_i \le 10000,1\le v_i\le 10000，1\le w\le 10000，1\le s\le 100$

来源

童程童美