19855번 - 3분 그래프 리턴즈

문제

3분 그래프라는 음식을 아는가? 3분 그래프는 서울대학교 컴퓨터공학부 학생들의 지친 심신을 위로해 주는 보양식으로, 이름에서 알 수 있듯 간편한 조리 방식과 깊은 풍미를 가지고 있어 널리 사랑받는 음식이다. 작년에 출시된 3분 그래프 평면맛의 인기에 힘입어, 3분 그래프 제조업체 스눕스는 야심작 3분 그래프 구간맛을 출시했다.

3-min-graph

3분 그래프 구간맛. 국산 정점을 쓴다.

3분 그래프 구간맛은 이름에서 알 수 있듯 정점이 N개인 구간 그래프의 형태이다. 각 정점은 위치가 고정된 수직선 상의 구간 형태이며, 겹치는 구간끼리는 간선으로 이어져 고정되어 있다. 끝점끼리 겹치는 구간도 겹치는 구간으로 생각한다. i번째 정점은 [s_i, e_i]의 구간으로 나타나며, t_i의 맛을 가지고 있다.

서울대학교 컴퓨터공학부는 아니지만 미식가인 규민이는 큰 마음을 먹고 3분 그래프 구간맛을 샀다. 그런데 규민이는 사이클 알러지가 있기 때문에, 정점을 몇 개 빼내서 모든 사이클을 제거한 뒤에 먹어야 한다. 물론 정점을 빼낼 때는 그 정점에 연결된 간선도 자연스럽게 제거된다.

규민이는 3분 그래프 구간맛을 최대한 맛있게 즐기고 싶기 때문에, 몇 개의 정점을 빼낸 뒤 남아 있는 정점들의 맛을 합한 값이 최대가 되었으면 한다. 규민이가 3분 그래프를 3분 안에 먹을 수 있도록 여러분이 이 작업을 대신 수행해주자.

입력

입력의 첫째 줄에는 구간의 개수 N이 주어진다.

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

출력

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

제한

• 1 ≤ N ≤ 250,000
• 1 ≤ s_i ≤ e_i ≤ 500,000, 1 ≤ t_i ≤ 10¹² (1 ≤ i ≤ N)

힌트