ストーリー

我们朝着敌人涌来的方向跑去。当我们击败敌人并顺着兽道前进时，发现一辆严重损坏的东西勉强看起来像是火车。

我突然感到焦虑，纠结于“必须前进”和“可以前进吗”的矛盾之中。

但还是向前，继续向前。

问题描述

有一列由 $N$ 辆车组成的火车。每辆车上有 $3$ 个零件，车辆 $k$ 的速度由零件 $A,B,C$ 的功率之和表示。

每个零件的功率范围是 $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$ 分。

---

输入

从标准输入读入数据，输入格式如下：

$N$ $F$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ : $A_N$ $B_N$ $C_N$

输出

输出改造零件的最小数量。

---

示例 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

---

解答

解答