CF777E.Hanoi Factory

Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings.

There are n rings in factory's stock. The i-th ring has inner radius a__i, outer radius b__i and height h__i. The goal is to select some subset of rings and arrange them such that the following conditions are satisfied:

• Outer radiuses form a non-increasing sequence, i.e. one can put the j-th ring on the i-th ring only if b__j ≤ b__i.
• Rings should not fall one into the the other. That means one can place ring j on the ring i only if b__j > a__i.
• The total height of all rings used should be maximum possible.

当然，你听说过著名的汉诺塔问题，但你是否知道，有一家专门生产这种神奇游戏所用圆环的工厂？很久以前，古埃及的统治者命令汉诺塔工厂的工人尽可能建造一座最高的塔。工人们不愿为这样奇怪的订单专门生产新圆环，因此他们只能利用工厂中已有的圆环来搭建这座新塔。

工厂库存中有 $n$ 个圆环。第 $i$ 个圆环的内半径为 $a_i$、外半径为 $b_i$、高度为 $h_i$。目标是选出若干个圆环并将其堆叠，使得满足以下条件：

• 外半径构成一个非递增序列，即：仅当 $b_j \leq b_i$ 时，才可将第 $j$ 个圆环放在第 $i$ 个圆环之上；
• 圆环不能彼此嵌套，即：仅当 $b_j > a_i$ 时，才可将第 $j$ 个圆环放在第 $i$ 个圆环之上；
• 所选圆环的总高度应尽可能大。

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of rings in factory's stock.

The i-th of the next n lines contains three integers a__i, b__i and h__i (1 ≤ a__i, b__i, h__i ≤ 109, b__i > a__i) — inner radius, outer radius and the height of the i-th ring respectively.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$）—— 工厂库存中圆环的数量。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $h_i$（$1 \leq a_i, b_i, h_i \leq 10^9$，且 $b_i > a_i$）—— 分别表示第 $i$ 个圆环的内半径、外半径和高度。

Print one integer — the maximum height of the tower that can be obtained.

输出一个整数——所能得到的塔的最大高度。

In the first sample, the optimal solution is to take all the rings and put them on each other in order 3, 2, 1.

In the second sample, one can put the ring 3 on the ring 4 and get the tower of height 3, or put the ring 1 on the ring 2 and get the tower of height 4.

在第一个样例中，最优解是取走所有圆环，并按 3、2、1 的顺序将它们叠放在一起。

在第二个样例中，可以将圆环 3 放在圆环 4 上，得到高度为 3 的塔；或者将圆环 1 放在圆环 2 上，得到高度为 4 的塔。