题目描述

你有 $N$ 个物品和一个容量为 $W$ 的背包。第 $i$ 个物品的重量为 $w_i$，价值为 $v_i$。

你可以选择其中一些物品放入背包，但所选物品的总重量必须小于等于 $W$。

你的目标是最大化放入背包中物品的价值总和。

输入格式

输入以以下格式从标准输入中给出：

$N$ $W$ $w_1$ $v_1$ $w_2$ $v_2$ … $w_N$ $v_N$

输出格式

输出最大价值总和。

样例 1

输入

4 6
2 1
3 4
4 10
3 4

输出

11

样例 2

输入

4 6
2 1
3 7
4 10
3 6

输出

13

样例 3

输入

4 10
1 100
1 100
1 100
1 100

输出

400

样例 4

输入

4 1
10 100
10 100
10 100
10 100

输出

0

说明/提示

限制条件

• $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 翻译