题目描述

你有一个容量为 $W$ 的背包，以及 $n$ 件物品。

第 $i$ 件物品的重量为 $w_i$，价值为 $v_i$。每件物品 最多只能选择一次。

你可以从这 $n$ 件物品中选出若干件放入背包，但要求所选物品的总重量不超过背包容量 $W$。

请你求出：在不超过容量限制的前提下，能够获得的最大总价值。

输入格式

第一行输入两个整数 $n, W$。

接下来 $n$ 行，每行输入两个整数 $w_i, v_i$。

数据范围：

$$1 \le n \le 100$$ $$1 \le W \le 10^5$$ $$1 \le w_i \le W$$ $$1 \le v_i \le 10^9$$

输出格式

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

3 8
3 30
4 50
5 60

90

Hint

样例解释： 选择第 $1$ 件和第 $2$ 件物品时，总重量为：

$$3+4=7$$

总价值为：

$$30+50=80$$

选择第 $1$ 件和第 $3$ 件物品时，总重量为：

$$3+5=8$$

总价值为：

$$30+60=90$$

因此最大总价值为 $90$。