给定 $N$ 个闭区间。第 $i$ 个区间的范围是 $[s_i, e_i]$，且具有一个正整数权重 $w_i$。

考虑一个包含 $N$ 个顶点的无向图，其中每个顶点对应一个区间，当且仅当两个区间对应的顶点之间存在非空交集时，它们之间存在一条边。对于给定的区间列表，我们将此图称为区间图。

Jaehyun 沉迷于关于树和查询的问题，因此他希望这个图是无环的。为了实现这一点，他可以删除零个或多个区间。Jaehyun 很懒，所以他会在所有可能的删除区间的方式中，选择一种使他必须删除的区间权重之和最小的方式。请输出在 Jaehyun 将区间图变为无环后，剩余区间的权重之和。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 250\,000$)。

接下来 $N$ 行，每行包含三个空格分隔的整数 $s_i, e_i, w_i$ ($1 \le s_i \le e_i \le 500\,000, 1 \le w_i \le 10^{12}$)。

输出格式

输出 Jaehyun 删除区间后，剩余区间的权重之和。

样例

输入 1

3
1 3 10
3 5 20
5 7 30

输出 1

60

输入 2

3
1 3 1
2 3 2
3 3 3

输出 2

5