問題文

$N$ 個の石があります。 $i$ 番目の石のタイプは $t_i$ であり、重量は $w_i$ 、 価値は $v_i$ です。ここで $t_i$ は $0$ か $1$ のどちらかです。

あなたは合計の重量が $W$ 以下になるようにいくつかの石を選んで箱に入れますが、タイプ $0$ の石の総重量とタイプ $1$ の石の総重量の差が $D$ 以下でなければなりません。

この条件を満たすように石を選ぶとき、価値の総和の最大値を求めてください。

制約

• $1 \le N \le 5000$
• $1 \le W \le 5000$
• $1 \le D \le 5000$
• $1 \le w_i \le 5000$
• $1 \le v_i \le 5000$
• $t_i \in \{0,1\}$
• 入力は全て整数

入力

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

$N$ $W$ $D$
$t_1$ $w_1$ $v_1$
$\vdots$
$t_N$ $w_N$ $v_N$

出力

答えを出力せよ。

サンプル

5 10 2
0 3 1
0 3 2
1 4 3
1 2 4
1 5 5

7

5 100 1
1 3 1000
1 4 2000
1 2 3000
1 5 4000
1 8 5000

0