Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1156.

Problem Description

Xiao Yang has $n$ horizontal platforms in a 2D space, and the platforms do not overlap with each other. The $i$-th platform is at height $h_i$, and its left and right endpoints are at $l_i$ and $r_i$, respectively.

Xiao Yang can move left and right on a platform. When Xiao Yang reaches the right endpoint, if he moves further right, he will fall vertically and land on the first platform below. The same applies to the left endpoint. Each time Xiao Yang moves $1$ unit of horizontal distance on a platform, it costs $1$ unit of time. While falling, each $1$ unit of height also costs $1$ unit of time.

Xiao Yang wants to know the minimum time needed to start from the left endpoint of the $s$-th platform and reach the $t$-th platform.

Note: It may be impossible to reach the $t$-th platform from the $s$-th platform.

Input Format

The first line contains a positive integer $n$, representing the number of platforms.

The second line contains two positive integers $s, t$, as described in the statement.

The next $n$ lines each contain three positive integers $l_i, r_i, h_i$, representing the left endpoint, right endpoint, and height of the $i$-th platform.

Output Format

Output one integer representing the minimum time required. If it is impossible to reach, output $-1$.

3
3 1
5 6 3
3 5 6
1 4 100000

100001

Hint

Sample Explanation

The minimum-time movement plan is: move from the left endpoint of platform $3$ to its right endpoint, costing $3$ units of time; then move right and fall onto platform $2$, costing $100000 - 6 = 99994$ units of time; then move right by $1$ unit of distance, costing $1$ unit of time; finally move right and fall onto platform $1$, costing $3$ units of time. The total cost is $100001$ units of time.

Constraints

For all testdata, it is guaranteed that $1 \leq n \leq 1000$, $1 \leq l_i \leq r_i \leq 10^5$, and $1 \leq h_i \leq 10^5$.

Translated by ChatGPT 5