AT_abc383_f [ABC383F] Diversity

[problemUrl]: https://atcoder.jp/contests/abc383/tasks/abc383_f 店で $ N $ 個の商品が売られています。 $ i $ 個目の商品の価格は $ P_i $ 円、効用は $ U_i $ 、色は $ C_i $ です。 あなたは、これらの $ N $ 個の商品から何個か( $ 0 $ 個でもよい)を選んで購入します。 このとき、購入した品物の合計価格は $ X $ 円以下でなければなりません。 あなたの満足度は、購入した商品の効用の合計を $ S $、購入した商品の色の種類数を $ T $ としたとき、$ S+T\ \times\ K $ です。 ここで、$ K $ は入力で与えられる定数です。 あなたの満足度を最大化するように購入する商品を選んだとき、満足度を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ K $ $ P_1 $ $ U_1 $ $ C_1 $ $ P_2 $ $ U_2 $ $ C_2 $ $ \vdots $ $ P_N $ $ U_N $ $ C_N $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 500 $ - $ 1\ \leq\ X\ \leq\ 50000 $ - $ 1\ \leq\ K\ \leq\ 10^9 $ - $ 1\ \leq\ P_i\ \leq\ X $ $ (1\ \leq\ i\ \leq\ N) $ - $ 1\ \leq\ U_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N) $ - $ 1\ \leq\ C_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ N) $ - 入力は全て整数 ### Sample Explanation 1 $ 1 $ 個目、$ 2 $ 個目の商品を購入したとき、効用の合計 $ S $ は $ 7 $ で、色の種類数 $ T $ は $ 2 $ です。よって、満足度は $ 7+2\ \times\ 5\ =\ 17 $ です。また、満足度が $ 18 $ 以上になるような購入の仕方は存在しないため、答えは $ 17 $ です。 ### Sample Explanation 2 $ 2 $ 個目、$ 3 $ 個目、$ 4 $ 個目の商品を購入したとき、効用の合計 $ S $ は $ 35 $ で、色の種類数 $ T $ は $ 3 $ です。よって、満足度は $ 35+3\ \times\ 3\ =\ 44 $ です。また、満足度が $ 45 $ 以上になるような購入の仕方は存在しないため、答えは $ 44 $ です。