很快小明的生日到了,小明的父母为了给小明过一个开心的生日,叫小明到城里唯一的一间儿童商店购买小明喜欢的商品,商店里共有n种商品,商品i的总重量为w[i],商品i总价值为v[i],小明带了一个背包去商店,背包最多能装M的重量。其中(1 <= i <= N, 0 < w[i] < M)。现在请你编一个程序帮小明算一算:怎样装才能使背包中装入的商品价值最高(对于每种商品i可以只装该商品的一部分x[i],当然也只能获得部分的价值:(x[i]/w[i])*v[i])。
从文件beibao.in中读入数据,文件的第一行是两个正整数N和M,N表示商店共有N种商品,M表示小明背包的最大容量,接下来共有N行,每行有两个正整数w[i]和v[i]表示第i种商品的重量和第i种商品的价值。
结果输出到文件beibao.out中,只有一个正整数,表示小明能获得的最大价值,结果四舍五入到小数后第二位。
样例1:
3 590
75 27
48 90
1 76
输出:
193.00
3 21
6 14
10 8
18 20
30.67
Beibao.in
3 21 //有3种商品,背包的最大容量为21
6 14 //第1种商品的重量为6,总价值为14
10 8 //第2种商品的重量为10,总价值为8
18 20 //第3种商品的重量为18,总价值为20
Beibao.out
30.67
样例说明:第一种商品取重量为6,第三种商品取重量为15,故所得到的价值为:
(14/6)*6+(20/18)*15=30.67
说明:N为小于等于50的正整数,M为小于等于是1000的正整数,其余数据全部为小于100的正整数,注意结果四舍五入到小数后第二位。