5801: 2.3 阿里巴巴与四十大盗
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：363
解决：87
题目描述
有一天，阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时，远处突然出现一股烟尘，弥漫着直向上空飞扬，朝他这儿卷过来，而且越来越近。靠近以后，他才看清原来是一支马队，他们共有四十人，一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋，从丛林中一直来到那个大石头跟前，喃喃地说道：“芝麻，开门吧！”随着那个头目的喊声，大石头前突然出现一道宽阔的门路，于是强盗们鱼贯而入。阿里巴巴待在树上观察他们，直到他们走得无影无踪之后，才从树上下来。他大声喊道：“芝麻，开门吧！”他的喊声刚落，洞门立刻打开了。
他小心翼翼地走了进去，一下子惊呆了，洞中堆满了财物，还有多得无法计数的金银珠宝，有的散堆在地上，有的盛在皮袋中。突然看见这么多的金银财富，阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界，见识一下这些宝物，他想一种宝物只拿一个，如果太重就用锤子凿开，但毛驴的运载能力是有限的，怎么才能用驴子运走最大价值的财宝分给穷人呢？阿里巴巴陷入沉思中……
输入
样例的组数 t
t ( 0 < t < 100 )
宝物数量m和驴子的承载重量 n
w2 v2
...
wm vm
t ( 0 < t < 100 )
宝物数量m和驴子的承载重量 n
m n ( 0 < m, n < 10000 )
第i个宝物的重量和价值 ( 0 < wi, vi < 100 )
w1 v1 第i个宝物的重量和价值 ( 0 < wi, vi < 100 )
w2 v2
...
wm vm
输出
装入宝物的最大价值
样例输入 复制
1
6 19
2 8
6 1
7 9
4 3
10 2
3 4样例输出 复制
24.6