#2145. [2011 安徽省] 最高得分(maxvalue)
[2011 安徽省] 最高得分(maxvalue)
题目描述
三次方求和的问题,被卡卡西迎刃而解,芭比阿姨拿出钥匙,打开了她后花园的大门。卡卡西被眼前的景色惊呆了!她从未见过这么多珍奇的鲜花,还有她梦寐以求的在阳光下发出异样光彩的水晶珠,她慢慢向前走着,忽然被一小块花圃吸引住了。这块花圃中,满是各式各样闪闪发亮的字母水晶珠,卡卡西心想要是能从这花圃中取出自己想要的字母水晶珠串成项链,那该多好啊!卡卡西往右手边一看,有一个告示牌,上面写道:亲爱的朋友,如果你想从花圃中获取字母水晶珠,必须先完成如下游戏:
假设所有的字母水晶珠都可以采,每种字母水晶珠的单颗价值都是一样的,且采摘任意一颗水晶珠所需要的时间都是 秒,但是采摘水晶珠的总时间是有限的,那么应该如何选择自己所要的字母水晶珠,使得总价值最高呢?假设每种字母水晶珠的数量和总价值用 表示,其中 表示这种水晶珠总的数量, 表示所有这种水晶珠的总价值。例如一共有 种字母水晶珠,其数量和价值分别如下:(4,20)、(4,24)、(5,38),留给卡卡西采摘水晶珠的总时间是 秒,则选择后两种水晶珠全部摘取,第一种摘取一颗时,可得摘取的最大价值为 ,如果选择摘前两种水晶珠和两颗第三种水晶珠,所能得价值为 。小朋友,你能帮助卡卡西计算出给定时间内所能采摘水晶珠的最大价值,从而让她顺利进入花圃采摘字母水晶珠吗?
输入格式
共 行,第一行为两个整数 和 (中间用空格隔开),分别表示字母水晶珠种类数和总的采摘时间;
后面 行中,每行两个整数 和 (中间用空格隔开),分别表示这种字母水晶珠的总数量和总价值。
输出格式
一行,所能得到的最大价值,输出结果保留两位小数。
样例
3 10
4 20
4 24
5 38
67.00
数据范围
20% 的数据
60% 的数据
100% 的数据