CF269D Maximum Waterfall

Emuskald 受雇于人，按照最新的景观建筑潮流设计一座人工瀑布。一座现代的人工瀑布由多块水平面板构成，这些面板固定在一面宽阔平整的墙上。水从墙顶流下，依次流经面板，直至抵达墙底。 该墙高为 $t$，墙上共有 $n$ 块面板。每块面板是位于高度 $h_i$ 的一段水平线段，起点为 $l_i$，终点为 $r_i$。第 $i$ 块面板连接平面上的两点 $(l_i, h_i)$ 和 $(r_i, h_i)$。墙顶可以视为一块位于高度 $t$ 的面板，其端点为 $(-10^9, t)$ 和 $(10^9, t)$。同理，墙底可以视为一块高度为 $0$ 的面板，端点为 $(-10^9, 0)$ 和 $(10^9, 0)$。任意两块面板没有公共点。 Emuskald 清楚，为了让瀑布视觉效果美观，瀑布从面板 $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)$，即两面板水平投影重叠部分的长度。 Emuskald 决定让瀑布沿着一条从顶到底的单一路径流动。即水从顶部流到一块面板后，必定继续流向且只流向下一块更低的面板。则该瀑布的总流量定义为该路径上每对连续面板间最小的重叠长度。形式化地说： 1. 瀑布构成一条单独的面板路径（如下图所示）； 2. 瀑布的流量等于该路径上的最小流量。 为了打造一座出色的瀑布，Emuskald 必须最大化这个流量，但他面板太多，难以规划。下图展示了 Emuskald 想要的瀑布示例： （见题面配图）请帮助 Emuskald 保住声誉，找出这座瀑布的最大可能流水量。

第一行包含两个用空格分隔的整数 $n$ 和 $t$（$1\leq n\leq10^5$，$2\leq t\leq10^9$），分别表示不包含顶底面板的面板数量，以及墙的高度。接下来的 $n$ 行，每行包含三个用空格分隔的整数 $h_i$、$l_i$ 和 $r_i$（$0

输出一个整数，即瀑布可能达到的最大流水量。

第一个测试样例对应题面图示。 由 ChatGPT 5 翻译