問題文

きぬごし君は、朝ごはんのビュッフェに来ています。
ビュッフェには $N$ 種類の料理があり、それぞれジャンルが $x_i$ 、おいしさが $y_i$ 、腹持ちが $z_i$ です。
きぬごし君は $M$ おなかが空いていて、食べた料理の腹持ちの合計が $M$ を超えない限り食べられますが、 食品ロスを避けるため取った料理をすべて食べてもおなかがいっぱいにならないようにします。 つまり、食べた料理の腹持ちの合計が $M$ 以下まで食べられます。
きぬごし君には料理のジャンルによって好き嫌いがあり、和食は $A$ ,洋食は $B$ ,中華は $C$ 好きです。
料理のおいしさ $\times$ ジャンルの好きさ がきぬごし君の満足度になります。
きぬごし君は同じ料理をふたつ食べると飽きてしまうので、同じ料理は食べません。
食べた料理の満足度の合計としてありえる最大値を出力してください。

制約

$0 \leq N , M \leq 5000$
$1 \leq A , B , C \leq 1000$
$1 \leq x_i \leq 3$
$1 \leq y_i \leq 10^9$
$1 \leq z_i \leq M$
入力は全て整数

入力

• $N M$
• $A\space B\space C$
• $x_1 \space y_1 \space z_1$
• $x_2 \space y_2 \space z_2$
  ・
  ・
  ・
• $x_N \space y_N \space z_N$
  $x$ において、和食は $1$ 、洋食は $2$ 、中華は $3$ に当てはまります。

出力

食べた料理の満足度の合計としてありえる最大値を1行で出力し、改行してください。

サンプル

6 9
1 2 3
3 1 2
2 1 1
3 2 3
1 1 2
3 1 1
1 85 5

94

3,5,6番目の食べ物を食べるのが最善です。

0 0
1 1 1

0

ビュッフェには1つも料理がなかったようです。