主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 C: 浪漫的V8

问题 C: 浪漫的V8

时间限制: 1 Sec  内存限制: 128 MB  Special Judge
提交: 229  解决: 44
[提交][状态][讨论版]

题目描述

V8为了讨女朋友开心,给lx承包大活后面那个水塘。为了筹集资金,V8偷偷地溜进了一座古墓,发现在他面前有金光闪闪的若干小箱子,里面全都是金粉,作为横行于各种@#¥&场所的V8来说,辨别不同成色的金粉早已不在话下,很快,他就给这些金粉的价值做出了评估,可惜V8力气太小,只能带走V体积的金粉,现在告诉你这些小箱子的体积,和每个箱子里面金粉的价值,问V8最多能带走多少价值的金粉?

输入

多组数据
第一行一个T,表示数据组数
之后对于每组数据
第一行一个整数n(1<=n<=10^3),表示箱子的数量,
之后n行,每行两个整数v,w(0<v<=10^3,0<=w<=10^3),分别表示箱子的体积和里面金粉的价值。
最后一行一个整数V(0<=V<=10^3),表示V8能带走的最大体积。

输出

每组数据一行,每行一个浮点数,表示最大价值,保留小数点后四位。

答案的绝对误差不超过10^-4即判为正确。

样例输入

2
5
1 2
1 3
1 4
1 5
1 6
4
3
1 1
1 1 
1 1
5

样例输出

18.0000
3.0000

提示

[提交][状态][讨论版]