시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 256 MB 27 13 13 54.167%

문제

승민이는 세계 최고의 프로그래머로, 대회에 참여하기만 하면 1등을 한다는 것은 여러분 모두가 알고 있는 사실이다. 승민이는 상금을 벌기 위해 여러 프로그래밍 대회를 참여하기로 하였는데, 총 N개의 대회가 있다.

당연하지만, 시간이 겹치는 대회가 있다면 그 대회 여러개를 동시에 칠 수는 없을 것이다. 그렇기에 승민이는 N개의 대회가 시작하는 시간, 끝나는 시간, 그리고 상금이 주어지면 최대로 상금을 벌 수 있는 방법으로 대회를 치루기로 하였다. 당연하지만 승민이는 모든 대회에서 상금을 받을 수 있다. 또한, 이동 시간을 고려해서 전 대회가 끝나는 시간과 다음 대회가 시작하는 시간이 같으면 안 된다.

입력

첫 줄에 N이 주어진다. (1 ≤ N ≤ 3×105)

N개의 줄에 걸쳐 대회의 정보가 주어지는데, Si, Ei, Ci가 공백으로 구분되어 순서대로 주어진다. 이는 i번째 대회는 Si시간에 시작해 Ei시간에 끝나며 상금은 Ci라는 뜻이다. (0 ≤ Si < Ei ≤ 109, 1 ≤ Ci ≤ 103)

출력

승민이가 받을 수 있는 최대 상금을 출력한다.

예제 입력 1

2
0 3 3
3 5 2

예제 출력 1

3

예제 입력 2

7
1 11 6
6 27 7
21 24 7
21 28 5
24 28 1
25 27 2
27 30 7

예제 출력 2

20

출처