Hanoi Factory

你肯定听说过著名的游戏汉诺塔吧，但是你知道有一个神奇的工厂专门制造这种游戏塔上的环吗？很久之前，古埃及的裁定者命令“汉诺工厂”（上文提到的工厂）的工人制造一座尽可能高的汉诺塔，而他们没有做好准备去执行这样一个奇怪的命令，所以他们不得不用已经造好的环。 工厂储备有$n$个环，其内径为$a_i$，外径为$b_i$，高度为$h_i$。要求环的放置条件如下： - 塔的外半径从下至上为非递增序列，即越下面的环外径不能小于上面的环 - 环不能掉下来，即相邻两环上方的环的外径必须大于下面的环的内径 - 塔的高度必须最大 # 输入输出格式 ## 输入格式 第$1$行一个数$n$，代表环的数量 第$2$~$n-1$行，每行3个数$a_i,b_i,h_i$代表环的内径，外径，高度 ## 输出格式 一个整数，代表塔的最大高度 样例及数据范围见原文 Translated by Venus

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.

The first line of the input contains a single integer $ n $ ( $ 1<=n<=100000 $ ) — 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}<=10^{9} $ , $ b_{i}>a_{i} $ ) — inner radius, outer radius and the height of the $ i $ -th ring respectively.

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

3
1 5 1
2 6 2
3 7 3

6

4
1 2 1
1 3 3
4 6 2
5 7 1

4

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 $ .