Spy Satellites

Byteland (Bajtlandia) is going through yet another crisis, and the army has seized power. To end the civil war, the commanders only need to find and eliminate the last holdouts who rejected the new order. That, however, is not so easy. From the (more or less voluntary) reports of informants, a list of possible locations for the rebel base has been compiled. Long searches of those spots turned up nothing, so the plan is now to wait until the rebels reveal themselves. To avoid tipping them off, the surveillance is run by a network of spy satellites.

Byteland can be pictured as a two-dimensional landscape formed by joining points with distinct $x$ coordinates into a polyline.

A spy satellite can be placed only on the line $y = H$. Such a satellite observes exactly those points that can be joined to it by a straight segment that does not cross the curve of the landscape (merely touching the curve does not count as crossing). Compute the minimum number of satellites needed to observe every suspected rebel-base location at the same time.

The first line contains two integers $n$ and $H$ ($1 \le n \le 100000$, $1 \le H \le 1000000$) separated by a single space.

Each of the next $n$ lines describes one point of the landscape and contains three integers $x_i$, $y_i$, $z_i$ ($0 \le x_i \le 1000000$, $0 \le y_i < H$, $z_i \in \{0, 1\}$) separated by single spaces. The pair $(x_i, y_i)$ is the point's location; $z_i = 1$ means the rebels may be based there, and $z_i = 0$ means they are not.

You may assume that $y_1 = 0$ and $y_n = 0$, and that the points are given in strictly increasing order of the $x$ coordinate.

Print a single integer: the minimum number of satellites needed.

For the landscape shown in the figure, two satellites placed at $x = 31.\overline{6}$ and $x = 112$ are enough.