题目描述

有 $N$ 道配菜。

第 $i$ 道配菜的美味度为 $A_i$，体积为 $B_i$。

你需要从中选择若干道配菜，使得所选配菜的总体积不超过 $W$，并把它们装进便当盒。

请求出所选配菜总美味度的最大值。

输入格式

输入按以下格式从标准输入读入：

• $N$ $W$
• $A_1$ $B_1$
• $A_2$ $B_2$
• $\vdots$
• $A_N$ $B_N$

输出格式

输出答案。

4 13
4 5
3 3
5 9
8 6

12

如果把第 $1$ 道和第 $4$ 道配菜装进便当盒，总美味度为 $12$，总体积为 $11$。

3 99
1 100
10 100
100 100

0

你也可以什么都不装。

5 9
6 4
9 1
2 1
4 3
5 4

21

数据范围

• $1 \leq N \leq 20$

• $1 \leq W \leq 10^9$

• $1 \leq A_i, B_i \leq 10^9$

• 所有输入值均为整数。

• 来源：AtCoder ABC 479 C

子任务设置

• 子任务 1（30 分）：$W \le 10^4$。
• 子任务 2（70 分）：无特殊限制。