#2145. [2011 安徽省] 最高得分(maxvalue)

[2011 安徽省] 最高得分(maxvalue)

题目描述

    三次方求和的问题,被卡卡西迎刃而解,芭比阿姨拿出钥匙,打开了她后花园的大门。卡卡西被眼前的景色惊呆了!她从未见过这么多珍奇的鲜花,还有她梦寐以求的在阳光下发出异样光彩的水晶珠,她慢慢向前走着,忽然被一小块花圃吸引住了。这块花圃中,满是各式各样闪闪发亮的字母水晶珠,卡卡西心想要是能从这花圃中取出自己想要的字母水晶珠串成项链,那该多好啊!卡卡西往右手边一看,有一个告示牌,上面写道:亲爱的朋友,如果你想从花圃中获取字母水晶珠,必须先完成如下游戏:

    假设所有的字母水晶珠都可以采,每种字母水晶珠的单颗价值都是一样的,且采摘任意一颗水晶珠所需要的时间都是 11 秒,但是采摘水晶珠的总时间是有限的,那么应该如何选择自己所要的字母水晶珠,使得总价值最高呢?假设每种字母水晶珠的数量和总价值用 (A,B)(A,B) 表示,其中 AA 表示这种水晶珠总的数量,BB 表示所有这种水晶珠的总价值。例如一共有 33 种字母水晶珠,其数量和价值分别如下:(4,20)、(4,24)、(5,38),留给卡卡西采摘水晶珠的总时间是 1010 秒,则选择后两种水晶珠全部摘取,第一种摘取一颗时,可得摘取的最大价值为 67.0067.00,如果选择摘前两种水晶珠和两颗第三种水晶珠,所能得价值为 59.2059.20。小朋友,你能帮助卡卡西计算出给定时间内所能采摘水晶珠的最大价值,从而让她顺利进入花圃采摘字母水晶珠吗?

输入格式

    共 N+1N+1 行,第一行为两个整数 N(100N10000)N(100≤N≤10000)T(1T10000)T(1≤T≤10000)(中间用空格隔开),分别表示字母水晶珠种类数和总的采摘时间;

    后面 NN 行中,每行两个整数 S(1S100)S(1≤S≤100)V(1V100)V(1≤V≤100)(中间用空格隔开),分别表示这种字母水晶珠的总数量和总价值。

输出格式

一行,所能得到的最大价值,输出结果保留两位小数。

样例

3 10
4 20
4 24
5 38
67.00

数据范围

20% 的数据 100N500100≤N≤500

60% 的数据 100N999100≤N≤999

100% 的数据 100N10000100≤N≤10000