题目描述

题目译自 XXIV Olimpiada Informatyczna — I etap Flappy Bird

自从 Bajtazar 在手机上装了 Flappy Bird，他就沉迷其中，达到了炉火纯青的地步，连最难的关卡也能轻松通关。现在，他给自己定了个新目标：用最少的力气过关。他请你帮忙写一个程序，助他实现这个愿望。

为了做到这一点，Bajtazar 得先把游戏规则讲清楚。游戏中，玩家控制的小鸟时刻处于一个直角坐标系的点上。开始时，小鸟在 $(0,0)$，目标是到达任意第一坐标为 $X$ 的点就算胜利。

每秒钟，小鸟从点 $(x, y)$ 移动一次，有两种选择：如果你点击屏幕，小鸟飞到 $(x+1, y+1)$；如果你啥也不做，小鸟滑到 $(x+1, y-1)$。Bajtazar 可以在游戏一开始就点击屏幕，让小鸟移动到 $(1, 1)$；但如果不点击屏幕，小鸟会到达 $(1, -1)$。

路上有 $n$ 个障碍等着小鸟。每个障碍由两条禁区半直线组成，小鸟一旦撞上任意禁区点，游戏立刻结束，玩家失败。第 $i$ 个障碍用三个数 $\left(x_{i}, a_{i}, b_{i}\right)$ 表示，意思是点 $(x_{i}, y)$（当 $y \leq a_{i}$ 或 $y \geq b_{i}$ 时）属于禁区（下图中这些半直线被画成窄矩形）。

对于给定的障碍集合，Bajtazar 想知道最少需要敲几次屏幕才能赢。

输入格式

输入的第一行包含两个整数 $n$ 和 $X$ $(0 \leq n \leq 500000; 1 \leq X \leq 10^{9})$，分别表示障碍数量和终点坐标。

接下来的 $n$ 行描述障碍，每行三个整数 $x_{i}, a_{i}, b_{i}$ $(0 < x_{i} < X; a_{i} < b_{i}; a_{i}, b_{i} \in [-10^{9}, 10^{9}])$，表示第 $i$ 个障碍的位置。障碍按从左到右顺序排列，即 $x_{1} < x_{2} < \ldots < x_{n}$。

输出格式

若给定障碍无法获胜，输出一行 NIE。

否则，输出一个非负整数，表示赢得游戏所需的最少点击屏幕次数。

4 11
4 1 4
7 -1 2
8 -1 3
9 0 2

5

第一个样例的图示中，箭头标记了玩家点击屏幕的位置。小鸟在第 $5$ 次点击屏幕后到达目标。

1 2
1 -1 1

NIE

附加样例

1. $n=5, X=6$；
2. $n=0, X=10^{9}$，答案为 $0$；
3. $n=500000-1, X=10^{9}, x_{i}=1000 \cdot i, a_{i}=-1, b_{i}=2$，答案为 $249999500$。

数据范围与提示

详细子任务附加限制及分值如下表所示。