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