B2174 完全背包

你有一个容量为 $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$ 种物品的体积与价值。

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

#### 样例说明 #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$。