g6-08100. 仓库备货 未做

仓库里堆着 $n$ 种货物，第 $i$ 种每件重 $w_i$、价值 $v_i$，每种货物都堆了很高一摞，想出多少件就出多少件。今天来的货车最多装 $V$ 千克。这一车货物尽量挑值钱的装，总价值最大能有多少？

第一行两个整数 $n,V$。接下来 $n$ 行，每行两个整数 $w_i,v_i$。

一行一个整数，表示最大总价值。

输入 1

2 10
3 5
4 6

输出 1

16

装两件重 3、价值 5 的货物，再装一件重 4、价值 6 的货物：总重 $3+3+4=10$，总价值 $5+5+6=16$，是所有装法里最高的。

$1\le n\le 100$，$0\le V\le 10^6$，$1\le w_i\le 10^9$，$0\le v_i\le 10^9$，答案不超过 $10^{18}$。