1179: 部分背包问题

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:59 Solved:30

Description

给定一个能装最大重量为 M 的背包和 N 种食品,这 N 种食品如食盐,白糖,大米等可以部分取过来想取多少就取多少。

已知第 i 种食品的最多拥有 Wi 公斤,其商品价值为 Vi 元/公斤,编程确定一个装货方案,使得装入背包中的所有物品总价值最大。

Input

第一行两数 N 和 M ,分别表示食品种类和背包容量。

接下来N行,每行两个数 Wi 和 Vi ,分别表示第i种食品的最多拥有重量和价值。

Output

一行一个数表示最大价值。

Sample Input Copy

3 5
4 2
3 6
5 3

Sample Output Copy

24

HINT

 1≤N,M,Wi,Vi≤104

Source/Category