AT_abc390_e [ABC390E] Vitamin Balance

$ N $ 個の食べ物があり、それぞれの食べ物にはビタミン $ 1,2,3 $ のうちちょうど $ 1 $ つのみが含まれています。 具体的には、 $ i $ 個目の食べ物を食べると、ビタミン $ V_i $ が $ A_i $ だけ摂取でき、またカロリーが $ C_i $ だけ摂取されます。 高橋君は、摂取するカロリーが合計で $ X $ 以下となるように、 $ N $ 個の食べ物のうちいくつか（ $ 0 $ 個でも良い）を選んで食べることができます。 このとき、「ビタミン $ 1,2,3 $ のうちもっとも摂取量が少ないものの摂取量」としてあり得る最大の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ V_1 $ $ A_1 $ $ C_1 $ $ V_2 $ $ A_2 $ $ C_2 $ $ \vdots $ $ V_N $ $ A_N $ $ C_N $

高橋君が摂取カロリーの合計が $ X $ 以下となるように食べ物を食べたとき、「ビタミン $ 1,2,3 $ のうちもっとも摂取量が少ないものの摂取量」としてあり得る最大の値を出力せよ。

### Sample Explanation 1 それぞれの食べ物を食べると高橋君は次のものを摂取します。 - $ 1 $ 個目の食べ物を食べると、ビタミン $ 1 $ を $ 8 $ とカロリーを $ 5 $ だけ摂取する。 - $ 2 $ 個目の食べ物を食べると、ビタミン $ 2 $ を $ 3 $ とカロリーを $ 5 $ だけ摂取する。 - $ 3 $ 個目の食べ物を食べると、ビタミン $ 2 $ を $ 7 $ とカロリーを $ 10 $ だけ摂取する。 - $ 4 $ 個目の食べ物を食べると、ビタミン $ 3 $ を $ 2 $ とカロリーを $ 5 $ だけ摂取する。 - $ 5 $ 個目の食べ物を食べると、ビタミン $ 3 $ を $ 3 $ とカロリーを $ 10 $ だけ摂取する。 高橋君が $ 1 $ , $ 2 $ , $ 4 $ , $ 5 $ 個目の食べ物を食べると、 高橋君はビタミン $ 1 $ を $ 8 $ 、ビタミン $ 2 $ を $ 3 $ 、ビタミン $ 3 $ を $ 5 $ 、そしてカロリーを $ 25 $ だけ摂取します。 このとき、「ビタミン $ 1,2,3 $ のうちもっとも摂取量が少ないもの」はビタミン $ 2 $ であり、その摂取量は $ 3 $ です。 どのように食べ物を選んで食べても、摂取カロリーの合計が $ 25 $ 以下となるようにビタミン $ 1,2,3 $ すべてを $ 4 $ 以上摂取することはできないため、 $ 3 $ を出力します。 ### Constraints - $ 1\leq N \leq 5000 $ - $ 1\leq X \leq 5000 $ - $ 1\leq V_i\leq 3 $ - $ 1\leq A_i\leq 2\times 10^5 $ - $ 1\leq C_i\leq X $ - 入力はすべて整数