#P1040. 调配能量晶粉

调配能量晶粉

题目背景

小林负责给一艘探测飞船准备应急能源。仓库里存放着若干种能量晶粉,每种晶粉都有自己的总重量和总能量价值。

题目描述

仓库中共有 NN 种能量晶粉,第 ii 种晶粉的总重量为 mim_i,全部带走可以提供的总价值为 viv_i

小林有一个储能箱,最多只能装下重量为 TT 的晶粉。由于储能箱容量有限,他不一定能把所有晶粉全部装进去。

幸运的是,晶粉可以任意分割。也就是说,对于某一种晶粉,小林可以全部带走,也可以只带走其中一部分。若只带走一部分,那么得到的价值会按照重量等比例减少,单位重量价值保持不变。

请你计算,在储能箱承重不超过 TT 的情况下,小林最多可以获得多少总价值。

输入格式

第一行包含两个整数 N,TN,T,分别表示晶粉种类数和储能箱的最大承重。

接下来 NN 行,每行包含两个整数 mi,vim_i,v_i,表示第 ii 种晶粉的总重量和总价值。

输出格式

输出一个实数,表示小林最多可以获得的总价值。

答案保留两位小数。

样例

5 35
10 50
20 80
15 45
30 90
5 10
145.00

提示

样例1解释

第一种晶粉重量为 1010,价值为 5050;第二种晶粉重量为 2020,价值为 8080

先装入这两种晶粉后,储能箱已经装入重量 3030,还剩下 55 的容量。

接着可以从第三种晶粉中取出重量为 55 的部分。第三种晶粉总重量为 1515,总价值为 4545,所以取出重量为 55 的部分可以获得价值:

45×515=1545 \times \frac{5}{15}=15

因此最大总价值为:

50+80+15=14550+80+15=145

所以输出:

145.00145.00

数据范围

对于所有数据,满足:

1N1001 \le N \le 100 1T10001 \le T \le 1000 1mi,vi1001 \le m_i,v_i \le 100

所有晶粉都可以任意分割,分割后单位重量价值保持不变。