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

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.