A93769.背包选礼物

你打算在有限的背包容量内挑选若干件礼物。每件礼物都有重量和价值。每件礼物最多只能选一次。请在不超过背包总容量的前提下，使选中的礼物总价值最大。

第一行包含两个整数 $n, W$，分别表示礼物数量和背包容量。

接下来 $n$ 行，每行两个整数 $w_i, v_i$，表示第 $i$ 件礼物的重量和价值。

输出一个整数，为在总重量不超过 $W$ 的前提下能获得的最大总价值。

• $1 \le n \le 100$

• $1 \le W \le 100000$

• $1 \le w_i \le W$

• $1 \le v_i \le 10^9$

对于样例：
有三件礼物，容量 $W=7$。
选 ${3,4}$ 的总重量 $3+4=7$，总价值 $30+50=80$；
选 ${5}$ 的总价值 $60$；
选 ${3}$ 的总价值 $30$；
选 ${4}$ 的总价值 $50$。
最优是选 ${3,4}$，得到 $80$。