题目描述

在二维坐标系内有 $n$ 个平台（定义平台是一条两端点纵坐标相同的开线段，开线段指线段两个端点不算做线段本身）和一个铁球，铁球如果下面没有物体，则每秒会下落一个单位长度。

球每次落到某个平台上后，游戏者可以选择水平向左或水平向右滚，球滚动速度是每秒 $1$ 个单位长度。由于铁球的质量不太好，每次落下的高度不能超过 $h$。

设计一种策略，使得球尽快落到地面而不被摔碎。

假设地面高度为 $0$，且无限宽。球体积相对平台极小，可以看作一个质点。请注意，球滚动至平台的一个端点处即可下落，不需要滚动至下一个格子。例如下图，小球在 $(9,9)$ 处已经开始下落。

输入格式

第一行有两个整数，分别代表平台个数 $n$ 和最大下落高度 $h$。

第二行有两个整数 $x, y$，表示铁球起始时在坐标为 $(x, y)$ 的位置。

第 $3$ 到第 $(n + 2)$ 行，每行三个整数，第 $(i + 2)$ 行的整数 $h_i, l_i, r_i$ 分别代表第 $i$ 个平台的端点纵坐标 $h_i$ 和左右端点的横坐标 $l_i,r_i$。

输出格式

输出一行一个整数表示最小的坠落时间。

5 3
6 10
5 2 4
9 3 9
6 7 10
2 1 5
3 8 11

15

10 156
84 139
63 22 50
79 96 100
87 77 98
60 24 53
47 1 29
62 55 89
68 68 78
10 5 85
85 67 71
73 57 61

155

提示

数据规模与约定

对于全部的测试点，保证：

• $1 \leq n \leq 10^5$。
• $1 \leq x, y, h, h_i, l_i, r_i \leq 10^9$，$l_i \leq r_i$。
• 对于所有的 $h_i$，保证互不相同，$l_i$ 与 $r_i$ 也互不相同，且对于任意 $i \neq j$，保证 $l_i \neq r_j$ 。
• 数据保证有解，最终答案不超过 $10^9$。