在变色龙村居住着 $n$ 只变色龙，它们可以被看作位于二维平面上。第 $i$ 只变色龙位于 $(x_i, y_i)$，颜色为 $c_i$。

深夜时分，只有第一只变色龙是清醒的，而其他所有变色龙都在睡觉。

突然，第 $n$ 只变色龙有紧急情况需要被唤醒。唤醒变色龙需要物理接触。因此，要唤醒一只变色龙，另一只变色龙必须要么走到它的位置，要么伸出舌头触碰它。

变色龙可以向八个方向移动：上、下、左、右或对角线方向。具体来说，位于 $(x, y)$ 的变色龙可以在一秒钟内移动到以下位置之一：$(x-1, y-1), (x-1, y), (x-1, y+1), (x, y-1), (x, y), (x, y+1), (x+1, y-1), (x+1, y)$ 或 $(x+1, y+1)$。

此外，变色龙可以垂直或水平地伸出舌头。换句话说，位于 $(x, y)$ 的变色龙可以伸出舌头到达 $(x+c, y)$ 或 $(x, y+c)$，其中 $c$ 为任意（正或负）整数。伸出舌头不需要时间。然而，相同颜色的变色龙几乎看不见对方，这使得它们难以瞄准，因此它们不能向对方伸出舌头。

当舌头伸出时，路径上是否有其他变色龙并不重要；只有位于舌头目标位置的变色龙会被唤醒，路径上的其他变色龙不会受到干扰。变色龙也可以在不唤醒其他变色龙的情况下穿过它们的位置。

由于变色龙很困，它们在唤醒另一只变色龙后会立即在当前位置睡着。

确定唤醒第 $n$ 只变色龙所需的最少秒数。

输入格式

第一行包含两个整数：变色龙的数量 $n$ 和不同颜色的数量 $m$ ($2 \le n \le 10^5$; $1 \le m \le n$)。

接下来的 $n$ 行中，第 $i$ 行包含三个整数：第 $i$ 只变色龙的初始坐标 $x_i$ 和 $y_i$ 以及颜色 $c_i$ ($-10^9 \le x_i, y_i \le 10^9$; $1 \le c_i \le m$)。没有两只变色龙起始于同一点。每种颜色至少有一只变色龙。

输出格式

输出唤醒第 $n$ 只变色龙所需的最少时间（以秒为单位）。

样例

输入 1

7 3
-5 0 1
-3 3 2
6 10000 2
5 3 3
3 -7 3
0 3 2
7 0 1

输出 1

4

说明

以下是对样例的解释。通过以下方式，可以在 4 秒内唤醒第 7 只变色龙：

• 第 1 只变色龙先从 $(-5, 0)$ 走到 $(-3, 0)$ 用时 2 秒，然后伸出舌头到 $(-3, 3)$ 唤醒第 2 只变色龙。
• 第 2 只变色龙通过从 $(-3, 3)$ 伸出舌头到 $(5, 3)$ 唤醒第 4 只变色龙。第 6 只变色龙正睡在路径中间，但它没有受到干扰。
• 第 4 只变色龙先从 $(5, 3)$ 走到 $(6, 4)$ 用时 1 秒，然后伸出舌头到 $(6, 10000)$ 唤醒第 3 只变色龙。
• 第 3 只变色龙从 $(6, 10000)$ 走到 $(7, 9999)$ 用时 1 秒，然后伸出舌头到 $(7, 0)$ 唤醒第 7 只变色龙。