D： 優柔不断 - Indecision -

問題

えびちゃんは最近ギャルゲーにハマっていて、今の目標は二人のヒロインを同時に攻略することです。

えびちゃんはいくつかあるイベントを利用してヒロインからの好感度を高めることができますが、各イベントの対象として選べるヒロインはどちらか一人のみです。しかし、えびちゃんは選ばなかったヒロインに対してもフォローを忘れないので、もう片方のヒロインからの好感度もある程度は高めることができます。ただし、イベントには費用がかかるため、必ずしも全てのイベントを行えるわけではありません。

さて、優柔不断なえびちゃんは各イベントをどちらのヒロインと行うか（またはどちらとも行わないか）で迷っています。えびちゃんは片方のヒロインからの好感度だけが高くても他方が低ければ意味がないと思っているので、好感度が高くない方のヒロインからの好感度が最大となる選択が理想です。

このとき、好感度が高くない方のヒロインからの好感度の最大値を求めてください。すなわち、イベントおよび対象ヒロインの選択の結果、ふたりのヒロインからの好感度をそれぞれ A、B としたときの、min\{A, B\} として考えうる値の最大値を求めてください。ここで、行うことにしたイベントに掛かる費用の合計が予算を超えてはいけません。また、各ヒロインからの好感度の初期値は 0 です。

入力形式

N C
a_1 b_1 c_1
…
a_N b_N c_N

1 行目にはイベントの候補の数 N と予算 C が空白区切りで与えられる。

1+i 行目 (1 \leq i \leq N) には i 番目のイベントについて、それを行うヒロインの好感度の増分 a_i と他方のヒロインの好感度の増分 b_i、およびそれらにかかる費用 c_i が空白区切りで与えられる。

制約

出力形式

問題文中の理想的な選択の下で、好感度が高くない方のヒロインからの好感度の最大値を一行に出力せよ。

入力例1

3 4
3 2 2
2 1 1
2 1 1

出力例1

5

最初の二つのイベントを片方のヒロインと、最後のイベントをもう片方のヒロインと行うのが最善です。

入力例2

3 3
3 2 2
2 1 1
2 1 1

出力例2

4