问题 B: 最大价值

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:218 通过:65

题目描述

很快小明的生日到了,小明的父母为了给小明过一个开心的生日,叫小明到城里唯一的一间儿童商店购买小明喜欢的商品,商店里共有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的正整数,注意结果四舍五入到小数后第二位。