在玻璃谷（Glass Valley）的中心坐落着一座神秘的星之神庙，这里以收藏着如繁星般闪耀的魔法水晶而闻名。每颗水晶都蕴含着特殊的力量，只要不被触碰，它们就会发出耀眼的光芒，照亮整个山谷。
神庙守护者的每晚任务是：仅触碰位于居民指定范围内的水晶，同时满足所有居民的要求。每位居民的要求告诉守护者，在他们的就寝时间之前，哪些范围内的水晶必须保持闪耀，因为他们害怕黑暗。
守护者从神庙入口出发，必须仔细协调他的移动，以便在正确的时间熄灭水晶。水晶排列成一条直线，彼此间隔一米（第一颗水晶距离入口一米）。守护者可以以每秒一米的速度移动，并可以在需要时停下。守护者触碰并熄灭一颗水晶所需的时间可以忽略不计。给定居民的要求，神庙守护者想知道完成所有要求所需的最少秒数（守护者不需要回到起点）。
输入格式
第一行包含一个整数 $N$ ($1 \le N \le 5000$)，表示居民请求的数量。
接下来的 $N$ 行，每行包含整数 $l_i, r_i, t_i$ ($1 \le l_i \le r_i \le 10^{18}, 1 \le t_i \le 10^{18}$)，分别表示水晶范围的左边界、右边界以及居民的就寝时间。
输出格式
仅输出一行，表示守护者完成所有要求所需的最少时间（以秒为单位）。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 20 | $n \le 18, l_i = r_i$ 对于所有 $i = 1, 2, \dots, n$ |
| 2 | 25 | $l_i = 1$ 对于所有 $i = 1, 2, \dots, n$ |
| 3 | 55 | $l_i = r_i$ 对于所有 $i = 1, 2, \dots, n$ |
| 4 | 20 | 无附加限制 |
样例
输入格式 1
3 1 1 1 3 3 5 5 5 3
输出格式 1
7
输入格式 2
3 1 2 1 1 1 5 1 3 4
输出格式 2
6
说明
神庙守护者首先花费 3 秒到达第 3 颗水晶。然后，他等待 1 秒并熄灭第 3 颗水晶。之后，他花费 1 秒移动到第 2 颗水晶并将其熄灭。最后，他花费 1 秒到达第 1 颗水晶并将其熄灭。总共，他的旅程将持续 6 秒，这是完成所有要求所需的最少时间。
输入格式 3
3 6 6 6 8 8 7 9 9 9
输出格式 3
9