/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
高橋君は N 個のお菓子を持っています。 i = 1, 2, \ldots, N について、i 番目のお菓子の重さは w_i 、美味しさは v_i です。
高橋君は N 個のうち好きな個数（ 0 個でもよい）のお菓子を選んで、明日の遠足に持って行きます。 高橋君は 2 つのナップサックを持っており、遠足に持っていくお菓子はそれぞれ 2 つのナップサックのどちらかに入れなければなりません。 ただし、1 つ目のナップサックに入れるお菓子の重さの合計は A 以下でなければならず、 2 つ目のナップサックに入れるお菓子の重さの合計は B 以下でなければなりません。
高橋君が遠足に持っていくお菓子の美味しさの合計としてありえる最大値を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq A, B \leq 300
- 1 \leq w_i \leq 300
- 1 \leq v_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A B w_1 v_1 w_2 v_2 \vdots w_N v_N
出力
答えを出力せよ。
入力例 1
6 8 9 2 6 4 1 5 9 3 1 5 3 5 8
出力例 1
24
1 番目のお菓子と 3 番目のお菓子を 1 つ目のナップサックに入れ、
2 番目のお菓子と 6 番目のお菓子を 2 つ目のナップサックに入れます。
このとき、1 つ目のナップサックに入れたお菓子の重さの合計は w_1 + w_3 = 2 + 5 = 7 、
2 つ目のナップサックに入れたお菓子の重さの合計は w_2 + w_6 = 4 + 5 = 9 であり、入れたお菓子の重さの合計は、それぞれのナップサックの上限 A = 8, B = 9 を超えません。
また、遠足に持っていくお菓子の美味しさの合計は、v_1 + v_2 + v_3 + v_6 = 6 + 1 + 9 + 8 = 24 であり、これが最大です。
入力例 2
20 70 60 7 94 18 33 14 26 10 1 9 57 2 80 19 74 16 10 15 18 10 38 13 90 12 23 3 3 8 11 18 10 3 42 3 66 3 90 10 2 5 45
出力例 2
772
Score : 6 points
Problem Statement
Takahashi has N snacks. For i = 1, 2, \ldots, N, the i-th snack has a weight of w_i and a tastiness of v_i.
Takahashi is going to choose any number (possibly 0) of the N snacks to take on tomorrow's school trip. Takahashi has two knapsacks. Every snack he takes on the school trip should fit in one of the two knapsacks. Here, the sum of weights of snacks in the first knapsack should be at most A, and the sum of weights of snacks in the second knapsack should be at most B.
Find the maximum possible total tastiness of snacks that he can take on the school trip.
Constraints
- 1 \leq N \leq 100
- 1 \leq A, B \leq 300
- 1 \leq w_i \leq 300
- 1 \leq v_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B w_1 v_1 w_2 v_2 \vdots w_N v_N
Output
Print the answer.
Sample Input 1
6 8 9 2 6 4 1 5 9 3 1 5 3 5 8
Sample Output 1
24
He can put the 1-st and the 3-rd snacks in the first knapsack,
and the 2-nd and the 6-th snacks in the second knapsack.
Then, the sum of weights of the snacks in the first knapsack is w_1 + w_3 = 2 + 5 = 7,
and the sum of the snacks in the second knapsack is w_2 + w_6 = 4 + 5 = 9, which do not exceed the upper limits of the respective knapsacks, A = 8, B = 9.
The total tastiness of the snacks he will take on the school trip is v_1 + v_2 + v_3 + v_6 = 6 + 1 + 9 + 8 = 24, which is the maximum.
Sample Input 2
20 70 60 7 94 18 33 14 26 10 1 9 57 2 80 19 74 16 10 15 18 10 38 13 90 12 23 3 3 8 11 18 10 3 42 3 66 3 90 10 2 5 45
Sample Output 2
772