P3118 - 【例85.1】金银岛

Memory Limit：64 MB Time Limit：1.000 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

金银岛上有s种金属,每种金属重量不同，分别为

n_{1}

n_{2}

..,

n_{s}

，同时每种金属的价值也不同，分别为

v_{1}

v_{2}

..,

v_{s}

。一次带走的金属重量总和不能超过

w

，问最多能带走价值多少的金属？n注意：金属是可以被任意分割的，金属的价值和重量成正比。

第1行是测试数据的组数

k

，后面跟着

k

组输入。n每组测试数据占

3

行，第

1

行是一个正整数

w

(

1 < w \leq 10000

)，表示口袋承重上限。第

2

行是一个正整数

s

(

1 < s < 100

)，表示金属种类。第

3

行有

2 s

个正整数，分别为

n_{1}

v_{1}

n_{2}

v_{2}

,...,

n_{s}

v_{s}

,分别为第一种，第二种，…第

s

种金属的总重量和总价值(

1 \leq n_{i} \leq 10000

1 \leq v_{i} \leq 10000

)。

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

3118: 【例85.1】金银岛