AT_iroha2019_day4_f 道なき道を

[problemUrl]: https://atcoder.jp/contests/iroha2019-day4/tasks/iroha2019_day4_f $ N $ 両からなる汽車があります。 それぞれの車両には $ 3 $ つの部品があり、車両 $ k $ が出すことのできる速度はそれぞれの部品 $ A,B,C $ の持つパワー $ A_k,B_k,C_k $ の和で表されます。 どの部品も、$ 0 $ 以上 $ F $ 以下のパワーを持ちます。 汽車の各車両の出すことのできる速度が降順になっていないと、進む途中で汽車が崩壊してしまいます。 あなたといろはちゃんはなるべく少ない部品を改造して、汽車が崩壊しないようにしたいと思っています。改造しても、$ 0 $ 以上 $ F $ 以下のパワーを持った部品しか作ることはできません。 すべての $ i\

入力は以下の形式で標準入力から与えられます。 > $ N $ $ F $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ : $ A_N $ $ B_N $ $ C_N $

改造する部品の個数の最小値を出力してください。

### ストーリー 僕たちは敵の湧いてくる方角へと駆けた。敵を倒しながら獣道を行くと、酷く損傷して、辛うじて汽車のように見えるものがあった。 僕は急に、「行かねば」という焦燥感と、「行っていいのか」という不安との板挟みになった。 でも前へ、 それでも前へ。 ### 制約 - 入力はすべて整数 - $ 1\ \leq\ N\ \leq\ 2\times10^5 $ - $ 1\ \leq\ F\ \leq\ 10^{10} $ - $ 0\ \leq\ A_k,\ B_k,\ C_k\ \leq\ F $ (制約の上限が間違っていたため修正しました 修正日時 : 2019/05/03 19:06) ### 部分点 - $ N\ \leq\ 3000 $ を満たすテストケースすべてに正解した場合、$ 300 $ 点が与えられる。 ### 解説 [解説](https://img.atcoder.jp/iroha2019-day4/editorial-F.pdf) ### Sample Explanation 1 例えば、車両 $ 2 $ の部品 $ B $ のパワーを $ 85 $ に変えると、各車両の合計が $ 240,\ 185,\ 180 $ になり汽車が連結のまま進めるようになります。 ### Sample Explanation 2 例えば、車両 $ 1 $ の部品 $ B $ のパワーを $ 90 $ にして、車両 $ 4 $ の部品 $ C $ のパワーを $ 10 $ に変えると、各車両の合計が $ 170,\ 150,\ 130,\ 90 $ になり汽車が連結のまま進めるようになります。 ### Sample Explanation 3 全車両の出すことができる速度を同じにするのが最適な場合もあります。