题目描述

假设山洞中有 n 种宝物，每种宝物有一定重量 w 和相应的价值 v，小怪兽运载能力有限，只能运走 m 重量的宝物，一种宝物只能拿一样，宝物可以分割。那么怎么才能使小怪兽运走宝物的价值最大呢？

输入格式

共n+1行：
第1行：宝物数量 n 及小怪兽的承载能力 m；
之后n行，每个宝物的重量和价值，用空格分开。

输出格式

一行，结果，表示装入宝物的最大价值

样例数据

input

10 30 
2 8 
5 15 
8 20 
9 18 
5 8 
4 6 
5 7 
5 6 
5 5 
4 3

output

70.5

数据与说明

对于 30% 的数据，1≤n≤10, 1≤m≤10,1≤重量，价值≤10；
对于 70% 的数据，1≤n≤1000, 1≤m≤1000,1≤重量，价值≤1000；
对于 100% 的数据，1≤n≤1000000, 1≤m≤1000000,1≤重量，价值≤10000；