欧姆龙编程竞赛 2026（第 479 场 AtCoder Beginner Contest）
便当装盒AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)There are $N$ side dishes.
有 $N$ 道配菜。AI (CI翻译)
The $i$-th side dish has a deliciousness of $A_i$ and a volume of $B_i$.
第 $i$ 道配菜的美味度为 $A_i$，体积为 $B_i$。AI (CI翻译)
You will choose some of the side dishes so that the total volume of the chosen dishes is at most $W$, and pack them into a lunch box.
你要选择一些配菜，使它们的总体积不超过 $W$，并将它们装进便当盒中。AI (CI翻译)
Find the maximum possible total deliciousness of the chosen side dishes.
求所选配菜的美味度总和的最大值。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \leq N \leq 20$$1 \leq W \leq 10^9$$1 \leq A_i, B_i \leq 10^9$- All input values are integers.
$1 \leq N \leq 20$$1 \leq W \leq 10^9$$1 \leq A_i, B_i \leq 10^9$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N W
A_1 B_1
A_2 B_2
\vdots
A_N B_NN W
A_1 B_1
A_2 B_2
\vdots
A_N B_NOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
Input #1
4 13
4 5
3 3
5 9
8 6
Output #1
12
If you pack the $1$-st and $4$-th side dishes into the lunch box, the total deliciousness is $12$ and the total volume is $11$.
Input #2
3 99
1 100
10 100
100 100
Output #2
0
You may also pack no side dishes.
Input #3
5 9
6 4
9 1
2 1
4 3
5 4
Output #3
21
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。