CF269D.Maximum Waterfall

Emuskald was hired to design an artificial waterfall according to the latest trends in landscape architecture. A modern artificial waterfall consists of multiple horizontal panels affixed to a wide flat wall. The water flows down the top of the wall from panel to panel until it reaches the bottom of the wall.

The wall has height t and has n panels on the wall. Each panel is a horizontal segment at height h__i which begins at l__i and ends at r__i. The i-th panel connects the points (l__i, h__i) and (r__i, h__i) of the plane. The top of the wall can be considered a panel connecting the points ( - 109, t) and (109, t). Similarly, the bottom of the wall can be considered a panel connecting the points ( - 109, 0) and (109, 0). No two panels share a common point.

Emuskald knows that for the waterfall to be aesthetically pleasing, it can flow from panel i to panel j () only if the following conditions hold:

1. max(l__i, l__j) < min(r__i, r__j) (horizontal projections of the panels overlap);
2. h__j < h__i (panel j is below panel i);
3. there is no such panel k (h__j < h__k < h__i) that the first two conditions hold for the pairs (i, k) and (k, j).

Then the flow for is equal to min(r__i, r__j) - max(l__i, l__j), the length of their horizontal projection overlap.

Emuskald has decided that in his waterfall the water will flow in a single path from top to bottom. If water flows to a panel (except the bottom of the wall), the water will fall further to exactly one lower panel. The total amount of water flow in the waterfall is then defined as the minimum horizontal projection overlap between two consecutive panels in the path of the waterfall. Formally:

1. the waterfall consists of a single path of panels ;
2. the flow of the waterfall is the minimum flow in the path .

To make a truly great waterfall Emuskald must maximize this water flow, but there are too many panels and he is having a hard time planning his creation. Below is an example of a waterfall Emuskald wants:

Help Emuskald maintain his reputation and find the value of the maximum possible water flow.

埃穆斯卡尔德受聘根据景观设计的最新潮流设计一座人工瀑布。一座现代人工瀑布由固定在一面宽阔平坦墙体上的多个水平面板构成。水流从墙体顶部开始，逐级流经各面板，最终到达墙体底部。

墙体高度为 $t$，其上共有 $n$ 个面板。每个面板是一条位于高度 $h_i$ 处的水平线段，起始横坐标为 $l_i$，终止横坐标为 $r_i$。第 $i$ 个面板连接平面上的两点 $(l_i,\,h_i)$ 和 $(r_i,\,h_i)$。墙体顶部可视为一个连接点 $(-10^9,\,t)$ 与 $(10^9,\,t)$ 的面板；类似地，墙体底部可视为一个连接点 $(-10^9,\,0)$ 与 $(10^9,\,0)$ 的面板。任意两个面板之间无公共点。

埃穆斯卡尔德知道：为使瀑布具有美学吸引力，水流仅当满足以下条件时才能从面板 $i$ 流向面板 $j$（）：

1. $\max(l_i,\,l_j) < \min(r_i,\,r_j)$（两面板的水平投影存在重叠）；
2. $h_j < h_i$（面板 $j$ 位于面板 $i$ 下方）；
3. 不存在面板 $k$（满足 $h_j < h_k < h_i$），使得前两个条件对 $(i,\,k)$ 和 $(k,\,j)$ 这两对均成立。

此时，从 $i$ 到 $j$ 的水流流量（）等于 $\min(r_i,\,r_j) - \max(l_i,\,l_j)$，即二者水平投影重叠部分的长度。

埃穆斯卡尔德决定，在他设计的瀑布中，水流将沿唯一路径从顶部流向底部。若水流到达某个面板（墙体底部除外），则它将恰好下落至唯一一个更低的面板。于是，整座瀑布的总水流流量被定义为该路径中所有相邻面板对之间水平投影重叠长度的最小值。形式化地：

1. 瀑布由一条唯一的面板路径构成（）；
2. 瀑布的水流流量即为该路径中所有相邻面板对的水流流量的最小值（）。

为打造真正卓越的瀑布，埃穆斯卡尔德必须最大化这一水流流量；但面板数量太多，他难以规划自己的杰作。下图是一个埃穆斯卡尔德所期望的人工瀑布示例：

请帮助埃穆斯卡尔德维护其声誉，并求出最大可能的水流流量值。

The first line of input contains two space-separated integers n and t (1 ≤ n ≤ 105, 2 ≤ t ≤ 109), the number of the panels excluding the top and the bottom panels, and the height of the wall. Each of the n following lines contain three space-separated integers h__i, l__i and r__i (0 < h__i < t,  - 109 ≤ l__i < r__i ≤ 109), the height, left and right ends of the i-th panel segment.

It is guaranteed that no two segments share a common point.

输入的第一行包含两个用空格分隔的整数 $n$ 和 $t$（$1 ≤ n ≤ 10^5$，$2 ≤ t ≤ 10^9$），分别表示除顶部和底部面板外的面板数量，以及墙的高度。接下来的 $n$ 行中，每行包含三个用空格分隔的整数 $h_i$、$l_i$ 和 $r_i$（$0 < h_i < t$，$-10^9 ≤ l_i < r_i ≤ 10^9$），分别表示第 $i$ 个面板段的高度、左端点和右端点。

保证任意两个面板段不共享任何公共点。

Output a single integer — the maximum possible amount of water flow in the desired waterfall.

输出一个整数——所期望的瀑布的最大可能水流总量。

The first test case corresponds to the picture.

第一个测试用例对应于该图片。