19855번 - 3분 그래프 리턴즈

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

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)