#2211. [GESP202406 八级] 空间跳跃

[GESP202406 八级] 空间跳跃

Description

小杨在二维空间中有 nn 个水平挡板,并且挡板之间彼此不重叠,其中第 ii 个挡板处于水平高度 hih_i ,左右端点分别位 于 lil_irir_i

小杨可以在挡板上左右移动,当小杨移动到右端点时,如果再向右移动会竖直掉落,从而落到下方第一个挡板上, 移动到左端点时同理。小杨在挡板上每移动 11 个单位长度会耗费 11 个单位时间,掉落时每掉落 11 个单位高度也会耗 费 11 个单位时间。

小杨想知道,从第 ss 个挡板上的左端点出发到第 tt 个挡板需要耗费的最少时间是多少?

注意:可能无法从第 ss 个挡板到达到第 tt 个挡板。

Input Format

第一行包含一个正整数 nn ,代表挡板数量。

第二行包含两个正整数 s,ts,t ,含义如题面所示。

之后 nn 行,每行包含三个正整数 li,ri,hil_i,r_i,h_i ,代表第 ii 个挡板的左右端点位置与高度。

Output Format

输出一个整数代表需要耗费的最少时间,如果无法到达则输出 。

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

100001

Hint

样例解释

耗费时间最少的移动方案为,从第 33 个挡板左端点移动到右端点,耗费 33 个单位时间,然后向右移动掉落到第 22 个 挡板上,耗费 1000006=99994100000 - 6 = 99994 个单位时间,之后再向右移动 11 个单位长度,耗费 11 个单位时间,最后向右移动 掉落到第 11 个挡板上,耗费 33 个单位时间。共耗费 3+99994+1+3=1000013 + 99994 + 1 + 3 = 100001 个单位时间。

数据范围

子任务编号 数据点占比 nn 特殊条件
1 20%20\% 1000\leq 1000 li=1l_i = 1
2 40%40\% li=i,ri=i+1l_i=i,r_i=i+1
3 40% 40\%

对于全部数据,保证有 1n105,0ai11 \leq n \leq 10^5 , 0 \leq a_i \leq 1

Source

GESP八级202406