题目描述

数轴的每个正整数位置上都有一盏水晶灯，最初所有水晶灯都亮着。一名守卫在时刻 $0$ 位于原点。她可以沿数轴以每单位时间一个单位长度的速度移动，也可以在原地等待。当她位于某盏水晶灯的位置时，可以选择熄灭这盏灯，熄灭操作不消耗时间。

村民提出了 $n$ 个要求。第 $i$ 个要求由三个正整数 $l_i,r_i,t_i$ 描述：区间 $[l_i,r_i]$ 内的所有水晶灯最终都必须被熄灭，但其中任意一盏灯都不能在时刻 $t_i$ 之前被熄灭。

所有要求都必须满足。特别地，如果一盏灯同时处于多个要求指定的区间内，则必须遵守这些要求规定的全部时间限制。守卫只需要熄灭至少出现在一个指定区间内的灯，完成后不必回到原点。

你需要求出，守卫最早可以在什么时刻完成全部要求。

输入格式

输入的第一行包含一个正整数 $n$，表示要求的数量。

接下来 $n$ 行，其中第 $i$ 行包含三个正整数 $l_i,r_i,t_i$，依次表示第 $i$ 个要求指定区间的左右端点和允许熄灯的最早时刻。

输出格式

输出一行一个正整数，表示完成全部要求的最早时刻。

输入输出样例

3
1 1 1
3 3 5
5 5 3

7

3
1 2 1
1 1 5
1 3 4

6

说明/提示

样例 1 解释

守卫可以在时刻 $1$ 到达位置 $1$ 并熄灭该处的灯，在时刻 $5$ 到达位置 $5$ 并熄灭该处的灯，再于时刻 $7$ 返回位置 $3$ 并熄灭该处的灯，完成全部要求。

该样例满足测试点 $1\sim10$ 的约束条件。

样例 2 解释

守卫可以在时刻 $3$ 到达位置 $3$，等待到时刻 $4$ 后熄灭该处的灯，再于时刻 $5$ 到达位置 $2$ 并熄灯，最后于时刻 $6$ 到达位置 $1$ 并熄灯。因此答案为 $6$。

该样例满足测试点 $11\sim23$ 的约束条件。

样例 3

见附件中的 glow/glow3.in 与 glow/glow3.ans。

该样例满足测试点 $1\sim10$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1\le n\le5000$；
• 对于所有 $i$（$1\le i\le n$），均有 $1\le l_i\le r_i\le10^{18}$，$1\le t_i\le10^{18}$。

特殊性质 A：对于所有 $i$（$1\le i\le n$），均有 $l_i=r_i$。

特殊性质 B：对于所有 $i$（$1\le i\le n$），均有 $l_i=1$。

附件

下载附加样例（glow.zip）