/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 個のおかずがあります。
i 個目のおかずのおいしさは A_i、体積は B_i です。
あなたは、選んだおかずの体積の総和が W 以下となるようにいくつかのおかずを選び、弁当箱に詰めます。
選んだおかずのおいしさの総和として考えられる最大値を求めてください。
制約
- 1 \leq N \leq 20
- 1 \leq W \leq 10^9
- 1 \leq A_i, B_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
4 13 4 5 3 3 5 9 8 6
出力例 1
12
1 個目のおかずと 4 個目のおかずを弁当箱に詰めたとき、おいしさの総和は 12、体積の総和は 11 です。
入力例 2
3 99 1 100 10 100 100 100
出力例 2
0
おかずを 1 つも弁当箱に詰めないこともあります。
入力例 3
5 9 6 4 9 1 2 1 4 3 5 4
出力例 3
21
Score : 300 points
Problem Statement
There are N side dishes.
The i-th side dish has a deliciousness of A_i and a volume of B_i.
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.
Find the maximum possible total deliciousness of the chosen side dishes.
Constraints
- 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.
Input
The input is given from Standard Input in the following format:
N W A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Output the answer.
Sample Input 1
4 13 4 5 3 3 5 9 8 6
Sample 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.
Sample Input 2
3 99 1 100 10 100 100 100
Sample Output 2
0
You may also pack no side dishes.
Sample Input 3
5 9 6 4 9 1 2 1 4 3 5 4
Sample Output 3
21