1888 - Knapsack3

問題

価格が $c$ ,重さが $w$,美味しさが $y$ の$n$個のおかしがある。
重さの総和が$M_w$を超えないように、価格の総和が$M_c$を超えないように選んだときの美味しさの総和の最大値を求めよ。
同じおかしは1回しか選べない。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M_c$ $M_w$
$c_1$ $w_1$ $y_1$
$c_2$ $w_2$ $y_2$
 : 
$c_N$ $w_N$ $y_N$

$c_i$は$i$番目の価格、$w_i$は$i$番目の重さ、$y_i$は$i$番目の美味しさを表す。

出力

重さの総和が$M_w$、価格の合計が$M_c$を超えないようにおかしを選んだときの美味しさの総和の最大値を出力せよ。
出力の最後に改行を入れること。

制約

$1 \leq N \leq 300$

$0 \leq M_c,M_w \leq 300$

$0 \leq w_i,c_i,y_i \leq 300$

入力はすべて整数

部分点

部分点1は以下の制約を満たす。(点数の30%)

$0 \leq N \leq 20$

部分点2は以下の制約を満たす。(点数の40%)

$c_i = 0$($0 \leq i \leq N$)

入出力例

入力例1

3 30 30
10 20 5
20 10 3
20 20 10

出力例1

10

3つ目のおかしのみを選ぶのが最も美味しさの総和が大きいです。

入力例2

5 60 45
10 20 5
15 10 3
20 20 10
15 5 8
35 40 15

出力例2

23

1,3,4つ目のおかしを選ぶか、4,5つ目のおかしを選ぶのが最も美味しさの総和が大きいです。

入力例3

3 1 1
10 20 5
20 10 3
20 20 10

出力例3

0

どのおかしも選べません。