Falling Ball

You are given a 2D coordinate system with a steel ball and n platforms. A platform is defined as an open horizontal line segment whose two endpoints share the same y‐coordinate (note that the endpoints are not part of the platform). Initially, the ball is located at point \((x,y)\). When there is no platform or ground directly beneath it, the ball falls vertically at a speed of 1 unit per second. Each time the ball lands on a platform, you can choose to roll it horizontally left or right at a speed of 1 unit per second. However, because the ball is rather fragile, the vertical distance of any falling drop must not exceed \(h\); otherwise, the ball will be damaged.

Your task is to design a strategy that allows the ball to reach the ground (which is at height 0 and extends infinitely in the horizontal direction) as quickly as possible without exceeding the safe drop height \(h\>. Note that when rolling on a platform, reaching either endpoint is sufficient to initiate a fall (the ball does not have to roll to the next integer coordinate). For example, if the ball is at \((9,9)\) on a platform and the endpoint is at 9, it can immediately start falling from that endpoint.

If it is impossible to reach the ground safely (i.e. some drop would exceed \(h\)), output -1.

Note on physics:
1. When falling, the ball falls vertically. It will land on the highest platform strictly below its current height if its x-coordinate is in the open interval \((l, r)\) of that platform.
2. If the ball is not on any platform (or is exactly at a platform endpoint), it continues falling. When the ball is at a platform, you may choose which endpoint to roll to before falling again.

Mathematical formulas:
Each safe drop must satisfy:
\[ y_{current} - y_{next} \le h \] and falling time is equal to the vertical distance dropped, while rolling time equals the horizontal distance moved.

inputFormat

The first line of input contains four integers: x y n h, where \(x\) and \(y\) represent the initial coordinates of the ball, \(n\) is the number of platforms, and \(h\) is the maximum safe vertical drop.

Each of the following \(n\) lines contains three integers: l r y. This describes a platform with its two endpoints \((l,y)\) and \((r,y)\) (remember that the platform is the open interval \((l, r)\)).

outputFormat

Output a single integer representing the minimum time needed for the ball to reach the ground safely. If it is impossible to reach the ground safely, output -1.

sample

6 16 4 5
1 5 12
5 10 12
2 7 8
1 4 4

21