Problem G
Manhattan Shopping

Image from pxhere

After attending the ProgNova contest, Peter walks out of the school to enjoy a weekend of shopping in Manhattan!

Peter has a shopping list with $m$ different items (numbered $1$ to $m$) he wants to purchase. There are $n$ shopping malls in Manhattan. Each shopping mall sells one of these $m$ items. (All the items Peter wants to buy are super rare and exclusive!) The $i$-th shopping mall is located at $(x_ i, y_ i)$ and sells only item $t_ i$.

Peter is planning for his shopping route. He starts from his school, which is located at $(0, 0)$. A move from $(x_1, y_1)$ to $(x_2, y_2)$ is said to be vertical if $|x_1 - x_2| < |y_1 - y_2|$. Otherwise, the move is horizontal. Peter always moves directly to a shopping mall or his school from his current position. He does not stop anywhere else. Peter may move to a same position multiple times. After buying all the items on the list, Peter will return to his school.

Peter hates to move vertically and wants to make as few vertical moves as possible. What is the minimum number of vertical moves Peter has to make so as to purchase all the $m$ items? Peter does not care about his total travel distance, or the number of horizontal moves he makes.

Input

The first line has two integer $n$ ($1 \leq n \leq 3\cdot 10^5$) and $m$ ($1 \leq m \leq 16$). Each of the next $n$ lines contains three integers. The $i$-th line has $x_ i$, $y_ i$ ($|x|, |y| \leq 10^9$) and $t_ i$ ($1 \leq t \leq m$). No two shopping malls share a same location and no shopping mall is located at $(0, 0)$. It is guaranteed that every of the $m$ items is sold by at least one shopping mall.

Output

Output the minimum number of vertical moves Peter has to make.

3 2
1 1 2
1 2 1
-1 1 2

0

4 3
1 2 1
-1 2 2
-1 -2 2
-2 -4 3

3