AT_arc073_b [ABC060D] Simple Knapsack

你有 $N$ 个物品和一个容量为 $W$ 的背包。第 $i$ 个物品的重量为 $w_i$，价值为 $v_i$。 你可以选择其中一些物品放入背包，但所选物品的总重量必须小于等于 $W$。 你的目标是最大化放入背包中物品的价值总和。

输入以以下格式从标准输入中给出： > $N$ $W$ $w_1$ $v_1$ $w_2$ $v_2$ … $w_N$ $v_N$

输出最大价值总和。

## 限制条件 - $1 \leq N \leq 100$ - $1 \leq W \leq 10^9$ - $1 \leq w_i \leq 10^9$ - 对于所有 $i = 2,3,...,N$，有 $w_1 \leq w_i \leq w_1 + 3$ - $1 \leq v_i \leq 10^7$ - $W,\ w_i,\ v_i$ 均为整数 ## 样例解释 1 选择第 $1$、第 $3$ 个物品最佳。 ## 样例解释 2 选择第 $2$、第 $4$ 个物品最佳。 ## 样例解释 3 可以选择所有物品。 ## 样例解释 4 一个物品也不能选择。 由 ChatGPT 5 翻译