AT_past17_h 履修登録

ある大学では $ N $ 個の科目が開講されています。 $ i $ 番目の科目は履修するのに必要な労力が $ a_i $ で、時間割上で $ b_i $ 番目の時間に講義が行われ、履修すると $ c_i $ 単位を取得できます。 あなたはこれらの科目からいくつかを履修して合計で $ M $ 単位以上を取得する必要があります。ただし、時間割上で同じ時間に講義が行われる科目を同時に履修することはできません。 $ M $ 単位以上を取得することができるならばそのために必要な労力の合計の最小値を、できないならば `-1` を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ \vdots $ $ a_N $ $ b_N $ $ c_N $

$ M $ 単位以上を取得することができるならばそのために必要な労力の合計の最小値を、できないならば `-1` を出力せよ。

### Sample Explanation 1 $ 1,3 $ 番目の科目を履修すると、必要な労力の合計が $ 8 $ になります。これが最小値です。 なお、 $ 1,2 $ 番目の科目は同じ時間に講義が行われるので同時に履修することができません。 ### Sample Explanation 2 すべての科目を履修しても $ 100 $ 単位以上を取得することができません。 ### Sample Explanation 3 $ 2 $ つの科目は同じ時間に講義が行われるので同時に履修することができず、 $ 100 $ 単位以上を取得することができません。 ### Constraints - $ 1 \leq N, M \leq 5000 $ - $ 1 \leq a_i,b_i,c_i \leq 5000 $ - 入力はすべて整数