3분 그래프 리턴즈

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

요약

구간이 겹치면 간선이 생기는 그래프에서 사이클이 남지 않도록 정점을 제거할 때, 남은 정점의 맛 합이 최대가 되는 값을 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 세그먼트 트리, 구간
정답자: 아직 제출이 없습니다

문제

3분 그래프라는 음식을 아는가? 3분 그래프는 서울대학교 컴퓨터공학부 학생들의 지친 심신을 위로해 주는 보양식이다. 이름처럼 조리가 간편하고 풍미가 깊어 널리 사랑받는다. 작년에 나온 3분 그래프 평면맛이 인기를 끌자, 제조업체 스눕스는 야심작 3분 그래프 구간맛을 내놓았다.

3-min-graph

3분 그래프 구간맛은 국산 정점을 쓴다. 정점이 $N$ 개인 구간 그래프이며, 각 정점은 위치가 고정된 수직선 위의 구간이다. 겹치는 구간끼리는 간선으로 이어진다. 끝점끼리만 겹치는 구간도 겹치는 구간으로 본다. $i$ 번째 정점은 구간 $[s_i, e_i]$ 이고 맛은 $t_i$ 이다.

규민이는 사이클 알레르기가 있어서, 먹기 전에 정점을 몇 개 빼내 모든 사이클을 없애야 한다. 정점을 빼내면 그 정점에 연결된 간선도 함께 사라진다. 규민이는 맛을 최대한 즐기고 싶어 하므로, 정점을 빼낸 뒤 남은 정점들의 맛의 합이 최대가 되기를 원한다. 규민이가 3분 그래프를 3분 안에 먹을 수 있도록 이 작업을 도와주자.

입력

첫째 줄에 구간의 개수 $N$ 이 주어진다. 둘째 줄부터 $N$ 개의 줄에 걸쳐 각 구간의 정보가 주어진다. $(i+1)$ 번째 줄에는 세 정수 $s_i$ , $e_i$ , $t_i$ 가 공백을 사이에 두고 주어지며, 이는 $i$ 번째 구간이 $[s_i, e_i]$ 이고 맛이 $t_i$ 라는 뜻이다.

출력

첫째 줄에 규민이가 먹을 수 있는 정점들의 맛의 합의 최댓값을 출력한다.

제한

$1 \le N \le 250{,}000$

$1 \le s_i \le e_i \le 500{,}000$ , $1 \le t_i \le 10^{12}$ ( $1 \le i \le N$ )

예제2

예제 1
입력
```
3
1 3 10
3 5 20
5 7 30
```
예상 출력
```
60
```
예제 2
입력
```
3
1 3 1
2 3 2
3 3 3
```
예상 출력
```
5
```