Problem Description

In a two-dimensional coordinate system, there are $n$ platforms (defined as open line segments with identical y-coordinates at both endpoints, where the endpoints are not part of the segment) and an iron ball. If there is nothing beneath it, the ball will fall one unit length per second.

Each time the ball lands on a platform, the player can choose to roll it horizontally to the left or to the right, with a rolling speed of one unit length per second. Due to the poor quality of the iron ball, the height from which it falls cannot exceed $h$.

Design a strategy to ensure the ball reaches the ground as quickly as possible without breaking.

Assume the ground level is at height $0$ and is infinitely wide. The ball's volume is negligible compared to the platforms, and it can be considered as a point mass. Note that the ball can start falling once it reaches the endpoint of a platform, without needing to roll to the next grid. For example, in the diagram, the ball at $(9,9)$ has already started falling.

Input Format

The first line contains two integers, representing the number of platforms $n$ and the maximum drop height $h$.

The second line contains two integers $x, y$, indicating the initial coordinates $(x, y)$ of the iron ball.

From the third to the $(n + 2)$th line, each line contains three integers. The $(i + 2)$th line's integers $h_i, l_i, r_i$ represent the y-coordinate of the endpoints of the $i$th platform and the x-coordinates of its left and right endpoints, respectively.

Output Format

Output a single integer representing the minimum time to reach the ground.

Sample Input and Output

Input Sample #1

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

Output Sample #1

15

Input Sample #2

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

Output Sample #2

155

Notes

Data Size and Constraints

For all test cases, the following constraints apply:

• $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$.
• All $h_i$ are unique, and $l_i$ and $r_i$ are also unique. For any $i \neq j$, $l_i \neq r_j$.
• The data guarantees a solution, and the final answer does not exceed $10^9$.

见题面 Input 部分

见题面 Output 部分