Blistavost

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

요약

시작점 0에서 출발해 직선 위를 1초에 1미터씩 움직이는 안내자가 각 구간의 취침 시각 이후에 구간 안의 모든 수정을 건드리는 최소 시간을 구합니다.

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

문제

전설의 계곡 한가운데에는 신비로운 별의 사원이 있다. 이곳에는 별처럼 빛나는 마법의 수정이 모여 있다. 각 수정은 특별한 힘을 지니며, 건드리지 않는 한 계곡 전체를 밝히는 빛을 낸다.

사원의 수호자는 매일 밤 계곡 주민들이 요청한 범위 안의 수정만 건드려야 하며, 모든 요청을 지켜야 한다. 각 요청은 어떤 범위의 수정이 주민의 취침 시각 이전에 꺼지면 안 되는지를 알려 준다. 주민들이 어둠을 무서워하기 때문이다.

수호자는 사원 입구에서 출발해 각 수정이 알맞은 순간에 꺼지도록 이동 경로를 짜야 한다. 수정은 일직선으로 1미터 간격으로 놓여 있으며, 첫 번째 수정은 입구에서 1미터 떨어져 있다. 수호자는 초당 1미터의 속도로 움직이고, 필요하면 언제든 멈출 수 있다. 수정에 닿아 끄는 데 걸리는 시간은 무시한다. 수호자는 출발 지점으로 돌아올 필요가 없다.

모든 요청을 만족하는 데 필요한 최소 시간(초)을 구하라.

입력

첫 줄에 정수 $N$ ( $1 \le N \le 5000$ )이 주어진다. 요청의 개수이다.

이어지는 $N$ 개의 줄에는 정수 $l_i$ , $r_i$ , $t_i$ ( $1 \le l_i \le r_i \le 10^{18}$ , $1 \le t_i \le 10^{18}$ )가 한 줄에 하나씩 주어진다. 각각 수정 범위의 왼쪽 끝, 오른쪽 끝, 그리고 주민의 취침 시각이다.

출력

모든 요청을 만족하는 데 필요한 최소 시간(초)을 한 줄에 출력한다.

예제3

예제 1
입력
```
3
1 1 1
3 3 5
5 5 3
```
예상 출력
```
7
```
예제 2
입력
```
3
1 2 1
1 1 5
1 3 4
```
예상 출력
```
6
```
예제 3
입력
```
3
6 6 6
8 8 7
9 9 9
```
예상 출력
```
9
```