능숙한 영업사원

면접 대비

시간 제한1초메모리 제한1024 MB

요약

시간이 겹치지 않는 회의를 골라 기대 이익의 합이 최대가 되도록 구하는 문제입니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 이분 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

한별은 경력이 많은 영업사원이다. 그녀에게는 여러 회사와 잡혀 있는 미팅 기회가 $N$ 개 있고, 그중 일부를 골라 참석하려고 한다. 신입 시절에는 가능한 한 많은 미팅에 나가는 것이 목표였다. 지금은 베테랑이 되어 어떤 미팅이 더 중요하고 어떤 미팅이 덜 중요한지 알고 있다.

한별은 각 미팅의 시작 시각과 종료 시각, 그리고 참석했을 때 얻을 기대 수익을 알고 있다. 두 미팅은 한쪽의 종료 시각이 다른 쪽의 시작 시각보다 늦을 때만 겹친다. 한 미팅이 끝나는 시각과 다음 미팅이 시작하는 시각이 정확히 같으면 두 미팅 모두 참석할 수 있다.

한별의 기대 수익 합이 최대가 되도록 미팅 일정을 고르는 프로그램을 작성하라.

입력

첫째 줄에 미팅 기회의 수 $N$ 이 주어진다. ( $1 \le N \le 100\,000$ )

다음 $N$ 개 줄의 $i$ 번째 줄에는 $i$ 번째 미팅의 시작 시각 $s_i$ , 종료 시각 $e_i$ , 기대 수익 $p_i$ 가 공백으로 구분된 정수로 주어진다. ( $0 \le s < e \le 10^9$ ; $1 \le p \le 10^9$ )

출력

한별이 미팅 일정을 최적으로 짰을 때 얻는 기대 수익의 합을 출력한다.

예제2

예제 1
입력
```
4
1 5 1
2 4 1
6 8 1
5 12 1
```
예상 출력
```
2
```
예제 2
입력
```
4
1 5 7
2 7 16
6 8 18
7 12 6
```
예상 출력
```
25
```