题目描述

你有一个容量为 $V$ 的背包，以及 $n$ 种物品。第 $i$ 种物品的体积为 $w_i$，价值为 $val_i$。

每种物品都有无限件，你可以选择任意多件放入背包，但总容量不能超过 $V$。

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

形式化题意：设第 $i$ 种物品选择 $x_i$ 件（$x_i$ 为非负整数），则需要满足：

$$\sum_{i=1}^{n} x_i \cdot w_i \le V,\quad x_i \ge 0$$

最大化目标：

$$\max \sum_{i=1}^{n} x_i \cdot val_i$$

输入格式

第一行两个整数 $n, V$，表示物品种类数与背包容量。

接下来 $n$ 行，每行两个整数 $w_i, val_i$，分别表示第 $i$ 种物品的体积与价值。

输出格式

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

3 10
2 3
3 4
4 5

15

提示

样例说明 #1

一种最优方案是选择第 1 种物品 $5$ 件：

• 总体积 $5 \times 2 = 10 \le 10$
• 总价值 $5 \times 3 = 15$

数据范围

对于 $40\%$ 的数据，$1\le n \le 8$，$1\le V \le 12$，且对所有 $i$，$1\le w_i \le 1000$，$0\le val_i \le 1000$。

对于 $100\%$ 的数据，$1\le n \le 1000$，$1\le V \le 1000$，且对所有 $i$，$1\le w_i \le 1000$，$0\le val_i \le 1000$。