ストーリー

僕たちは敵の湧いてくる方角へと駆けた。敵を倒しながら獣道を行くと、酷く損傷して、辛うじて汽車のように見えるものがあった。

僕は急に、「行かねば」という焦燥感と、「行っていいのか」という不安との板挟みになった。

でも前へ、 それでも前へ。

問題文

N 両からなる汽車があります。 それぞれの車両には 3 つの部品があり、車両 k が出すことのできる速度はそれぞれの部品 A,B,C の持つパワー A_k,B_k,C_k の和で表されます。

どの部品も、0 以上 F 以下のパワーを持ちます。

汽車の各車両の出すことのできる速度が降順になっていないと、進む途中で汽車が崩壊してしまいます。

あなたといろはちゃんはなるべく少ない部品を改造して、汽車が崩壊しないようにしたいと思っています。改造しても、0 以上 F 以下のパワーを持った部品しか作ることはできません。
すべての i<j に対して、(車両 i が出すことのできる速度) \geq (車両 j が出すことのできる速度) となるように、改造する部品の個数の最小値を求めてください。

制約

• 入力はすべて整数
• 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 点が与えられる。

入力例 1

3 100
80 100 60
30 50 70
90 10 80

出力例 1

1

例えば、車両 2 の部品 B のパワーを 85 に変えると、各車両の合計が 240, 185, 180 になり汽車が連結のまま進めるようになります。

入力例 2

4 100
30 10 40
10 50 90
20 60 50
30 50 80

出力例 2

2

例えば、車両 1 の部品 B のパワーを 90 にして、車両 4 の部品 C のパワーを 10 に変えると、各車両の合計が 170, 150, 130, 90 になり汽車が連結のまま進めるようになります。

入力例 3

4 100
0 0 0
0 0 100
100 100 0
100 100 100

出力例 3

4

全車両の出すことができる速度を同じにするのが最適な場合もあります。

入力例 4

10 100
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49
100 37 49

出力例 4

0

入力例 5

5 10000000000
1701355307 429870732 6220675835
286943432 6531822025 3789827719
2265045229 9897189805 5070400071
8975758188 6810134144 5515765460
7476103030 3953670242 7426723712

出力例 5

4

解説

解説