시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB3510952.941%

문제

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

3-min-graph

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

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

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

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

입력

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

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

출력

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

제한

  • 1 ≤ N ≤ 250,000
  • 1 ≤ siei ≤ 500,000, 1 ≤ ti ≤ 1012 (1 ≤ iN)

예제 입력 1

3
1 3 10
3 5 20
5 7 30

예제 출력 1

60

예제 입력 2

3
1 3 1
2 3 2
3 3 3

예제 출력 2

5