g6-08042. 行李打包 未做

下周小杨要去露营。妈妈允许他从家里带一些物品：家里共有 $n$ 种物品，第 $i$ 种每件重 $w_i$ 千克、价值 $v_i$ 元，并且每种都有很多件，想带几件就带几件。背包最多装 $W$ 千克。请在总重量不超过 $W$ 的前提下，让带走的物品总价值尽量大，输出这个最大值。

第一行两个整数 $n$、$W$。

接下来 $n$ 行，每行两个整数 $w_i$、$v_i$，表示第 $i$ 种物品的单件重量与单件价值。

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

输入 1

3 10
2 3
3 4
4 5

输出 1

15

带 5 件第一种物品：重量 $2\times 5=10$ 千克，价值 $3\times 5=15$ 元，是所有装法里最大的。

$1\le n\le 100$，$0\le W\le 2\times 10^4$，$1\le w_i\le 10^9$，$0\le v_i\le 10^9$。保证答案不超过 $10^{18}$。