科技节结束后,工作人员需要用一辆小车运输剩余的制作材料。小车最多承载 T 千克材料。
共有 n 批材料,第 i 批的总重量为 m_i 千克,总价值为 v_i 元。每批材料都可以任意分割;取走其中一部分时,其价值与重量成正比。
例如,取走一批材料重量的四分之一,就获得这批材料总价值的四分之一。
每批材料可以全部取走、取走一部分或不取,取走的总重量不能超过 T 千克,也不要求装满小车。
请计算最多可以运走多少元的材料。
第一行输入两个整数 n,T。
接下来 n 行,每行输入两个整数 m_i,v_i,分别表示一批材料的总重量和总价值。
输出一个实数,表示最多可以运走的总价值,四舍五入保留两位小数。
3 50 10 60 20 100 30 120
240.00
2 10 3 5 4 9
14.00
取走第 1、2 批的全部材料,再取第 3 批的 20 千克,总价值为 60+100+80=240 元。
全部材料只有 7 千克,可以全部运走。