贪心的自助餐
小B同学想去吃自助餐,但是他是那种比较节俭的的人,既不想浪费食物,又想尽可能吃的贵一点,他于是私下里做了调查。
小蓝餐厅的自助餐有 n 种食材,每种食材都有它的价格。
而且也能估计出每一份的重量,所以他列了一个表格:
菜品 | 价格(元) | 重量(g) |
---|---|---|
红烧牛肉 | 30 | 300 |
油闷大虾 | 8 | 5 |
四喜丸子 | 4 | 8 |
三文鱼 | 5 | 3 |
排骨 | 18 | 200 |
麻辣兔头 | 20 | 120 |
高汤海参 | 40 | 70 |
扇贝粉丝 | 8 | 32 |
牛排 | 79 | 240 |
小B的饭量为 C(g),他想知道在不超过饭量的情况下他最多能吃多少钱的菜品。
请你设计一个程序帮助小B计算他的最多吃了多少钱。(假设自助餐厅的菜品供应同样的菜品每个人只能取一份。)
第一行输入两个整数 n,C(0≤n≤103,0≤C≤104),其中 n 为菜品数量,C 为小B的肚子容量。
接下来 n 行每行输入两个数 v[i],w[i],v[i] 是第 i 个菜品的价值,w[i] 表示第 i 个菜品的重量(0≤v[i],w[i]≤104)。
输出一行数据,表示最大的价值,保留小数点后三位数。
>输入
20 1000
1 22
2 43
123 214
12 2
123 432
21 223
22 16
77 49
34 78
34 9
43 677
21 34
23 23
12 56
332 56
21 99
123 545
389 33
12 999
23 88
>输出
1204.114