시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB67363351.562%

문제

A prestigious politician aiming for presidency next year is planning a fundraising dinner for her campaign. She has a list of some wealthy people in the country and wants to invite them in a way that the amount of money raised is as great as possible.

Sometimes wealthy people have futile behavior and don’t like the idea that someone richer or prettier than them exists. Every time someone like this meets another person who is strictly prettier, but not strictly richer, then an argument ensues. Likewise, if they meet another person who is strictly richer, but not strictly prettier, an argument occurs as well. These two situations are the only possible causes of an argument involving two persons. Thus, two persons do not have an argument if one of them is strictly prettier and strictly richer than the other. Also, two persons do not have an argument if they are equally rich and equally pretty.

Since the presidential candidate wants to raise as much money as possible, an argument should be avoided at all costs, as it could ruin the campaign. Given the characteristics of some wealthy people in the country, you must find a guest list that maximizes the donations while ensuring that no argument will happen during the dinner.

입력

The first line contains an integer N (1 ≤ N ≤ 105) representing the number of possible guests with known characteristics. Each of the next N lines describes a possible guest with three integers B, F and D (1 ≤ B, F, D ≤ 109), indicating respectively the person’s beauty, his/her fortune, and how much this person will donate if invited.

출력

Output a single line with an integer indicating the maximum sum of donations if guests are invited so that no argument will happen during the dinner.

예제 입력 1

4
1 2 50
2 1 50
2 2 30
1 1 30

예제 출력 1

60

예제 입력 2

3
3 3 3
5 5 3
2 2 3

예제 출력 2

9

예제 입력 3

3
2 8 13
1 4 12
2 1 16

예제 출력 3

25

출처

ICPC > Regionals > Latin America > Latin America Regional Contests 2017 F번

  • 문제를 만든 사람: Paulo Cezar Pereira Costa