问题 D: 最大价值

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:189 通过:98

题目描述

昨晚小明做了一个梦,梦中他来到了一个花园,当他打开花园的大门时,小明被眼前的景色惊呆了!他从未见过这么多珍奇的鲜花,还有他梦寐以求的在阳光下发出异样光彩的水晶珠,他慢慢向前走着,忽然被一小块花圃吸引住了。这块花圃中,满是各式各样闪闪发亮的字母水晶珠,小明心想要是能从这花圃中取出自己想要的字母水晶珠串成项链,那该多好啊!小明往右手边一看,有一个告示牌,上面写着:亲爱的朋友,如果你想从花圃中获取字母水晶珠,必须先完成如下游戏。游戏规则如下:假设所有的字母水晶珠都可以采,每种字母水晶珠的单颗价值都是一样的,且采摘任意一颗水晶珠所需要的时间都是1秒,但是采摘水晶珠的总时间是有限的,那么应该如何选择自己所要的字母水晶珠,使得总价值最高呢?我们把每种字母水晶珠的数量和总价值用(A,B)表示,其中A表示这种水晶珠总的数量,B表示所有这种水晶珠的总价值,例如一共有3种字母水晶珠,则其数量和价值分别如下:(4,20)、(4,24)、(5,38),留给你采摘水晶珠的总时间是10秒,当你选择后两种水晶珠全部摘取、第一种摘取一颗时,可得摘取的最大价值为67.00,如果你选择摘前两种水晶珠和两颗第三种水晶珠时,则所得价值为59.20。
小朋友,你能帮助小明计算出给定时间内所能采摘水晶珠的最大价值,从而让他顺利进入花圃采摘字母水晶珠吗?

输入格式

共N+1行,第一行为两个整数N(1≤N≤100)和T(1≤T≤500)(中间用空格隔开),分别表示字母水晶珠种类数和总的采摘时间;后面N行中,每行两个整数S(1≤S≤50)和V(1≤V≤100)(中间用空格隔开),分别表示这种字母水晶珠的总数量和总价值。

输出格式

只有一行,表示所能得到的最大价值,结果保留两位小数。

输入样例 复制

3 10
4 20 
4 24 
5 38

输出样例 复制

67.00

数据范围与提示