Fundraising Dinner

Time limit1sMemory limit1024 MB

Summary

Choose a subset of people with beauty, fortune, and donation so that no two conflict, and the total donation is maximized.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Divide and conquer, Segment tree
Solved: No attempts yet

Problem

A politician running for president next year is planning a fundraising dinner for her campaign. She holds a list of wealthy people in the country and wants to invite them so that the amount of money raised is as large as possible.

Some wealthy people cannot stand the idea that someone richer or prettier than them exists. Every time such a person meets someone who is strictly prettier but not strictly richer, an argument starts. Meeting someone who is strictly richer but not strictly prettier starts an argument as well. These two situations are the only causes of an argument between two people. So two people do not argue if one of them is both strictly prettier and strictly richer than the other, and two people do not argue if they are equally rich and equally pretty.

An argument could ruin the campaign, so it has to be avoided at all costs. Given the characteristics of the possible guests, find the guest list that maximizes the total donation while no argument happens during the dinner.

Input

The first line contains an integer $N$ ( $1 \le N \le 10^5$ ), the number of possible guests whose characteristics are known. Each of the next $N$ lines describes one possible guest with three integers $B$ , $F$ and $D$ ( $1 \le B, F, D \le 10^9$ ): the person's beauty, the person's fortune, and the amount this person donates if invited.

Output

Print one line with a single integer, the maximum total donation over all guest lists that cause no argument during the dinner.

Examples3

Example 1
Input
```
4
1 2 50
2 1 50
2 2 30
1 1 30
```
Expected output
```
60
```
Example 2
Input
```
3
3 3 3
5 5 3
2 2 3
```
Expected output
```
9
```
Example 3
Input
```
3
2 8 13
1 4 12
2 1 16
```
Expected output
```
25
```