AT_past202306_j 忍者

ある忍者が $ N $ 体の魔物と一体ずつ順番に戦います。 $ i $ 番目の魔物の攻撃力は $ a_i $ 、体力は $ b_i $ であり、魔物は体力が $ 0 $ 以下になった瞬間に倒れます。 なお、魔物は地上にいるか飛んでいるかのどちらかであり、 $ x_i = 0 $ なら $ i $ 番目の魔物は地上におり、 $ x_i = 1 $ なら飛んでいます。 忍者は初め、 $ M $ 枚の手裏剣を持っています。それぞれの手裏剣は一度投げると二度と使えません。 忍者と $ i $ 番目の魔物は以下のように戦います。 - まず、忍者が持っている手裏剣から $ 0 $ 枚以上を選んで魔物に投げる。投げた枚数だけ魔物の体力が減り、飛んでいる魔物に $ 1 $ 枚以上の手裏剣を投げた場合、その魔物は地上に降りる。 - その後、忍者と魔物が交互に相手を攻撃する。忍者の攻撃により魔物の体力は $ 1 $ 減り、魔物の攻撃により忍者の体力は $ a_i $ 減る。なお、魔物が地上にいるなら忍者が先に攻撃し、飛んでいるなら魔物が先に攻撃する。 忍者の最初の体力と、全ての魔物を倒し終わった後の体力の差としてあり得る最小値を求めてください。 なお、忍者の体力は十分に大きいとします。

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

答えを出力せよ。

### Sample Explanation 1 忍者が以下のように戦うと、忍者の体力は合計で $ 4 $ 減少し、これが最適です。 - $ 1 $ 番目の魔物には手裏剣を投げない。 - 魔物は飛んでいるので、魔物が先に忍者を攻撃する。忍者の体力が $ 2 $ 減る。 - 忍者が攻撃する。魔物の体力が $ 1 $ になる。 - 魔物が攻撃する。忍者の体力が $ 2 $ 減る。 - 忍者が攻撃する。魔物は体力が $ 0 $ になり、倒れる。 - $ 2 $ 番目の魔物に手裏剣を $ 1 $ 枚投げる。魔物の体力は $ 1 $ になる。 - 魔物は地上にいるので、忍者が先に魔物を攻撃する。魔物は体力が $ 0 $ になり、倒れる。 ### Sample Explanation 2 忍者が以下のように戦うと、忍者の体力は合計で $ 1 $ 減少し、これが最適です。 - $ 1 $ 番目の魔物に手裏剣を $ 2 $ 枚投げる。魔物の体力は $ 2 $ になり、地上に降りる。 - 魔物は地上にいるので、忍者が先に魔物を攻撃する。魔物の体力が $ 1 $ になる。 - 魔物が攻撃する。忍者の体力が $ 1 $ 減る。 - 忍者が攻撃する。魔物は体力が $ 0 $ になり、倒れる。 ### Constraints - $ 1 \leq N \leq 3 \times 10^5 $ - $ 0 \leq M \leq 10^{11} $ - $ 1 \leq a_i, b_i \leq 3 \times 10^5 $ - $ x_i = 0 $ または $ x_i = 1 $ - 入力される値は全て整数