무빙워크

국제정보올림피아드에 참가하는 스웨덴 대표팀은 IOI 2020에 출전하기 위해 방금 싱가포르에 도착했다. 수하물 찾는 곳으로 가는 길에, 여러 무빙워크가 있는 긴 복도를 통과해야 한다. 복도의 길이는 $M$미터이며, 대표팀은 현재 복도 시작 지점에서 얼마나 빨리 수하물 찾는 곳에 도착할 수 있을지 알아보고 있다. 복도에는 $N$개의 무빙워크가 있다. 각 무빙워크는 복도 시작 지점에서 특정한 거리만큼 떨어진 곳에서 시작하고, 복도 시작 지점에서 특정한 거리만큼 떨어진 곳에서 끝나며, 그 위를 이동하는 데 일정한 시간이 걸린다. 모든 무빙워크는 복도를 따라가는 방향으로 움직이며, 무빙워크에는 시작 지점에서만 올라타고 끝 지점에서만 내릴 수 있다. 대표팀이 어떤 무빙워크에도 타고 있지 않을 때는 한 미터를 걷는 데 $g$초가 걸린다. 복도와 무빙워크는 충분히 좁으므로 복도와 평행한 방향으로 이동하는 데 걸리는 시간만 중요하다. 따라서 한 무빙워크가 끝나는 지점과 다른 무빙워크가 시작하는 지점이 복도 시작 지점에서 같은 거리만큼 떨어져 있다면, 두 무빙워크 사이를 이동하는 데 시간이 걸리지 않는다. 대표팀이 경로를 최적으로 계획한다면 복도 끝에 얼마나 빨리 도착할 수 있는가?

때로는 더 앞까지 데려다주는 무빙워크에 도달하기 위해 복도를 따라 뒤로 걷는 것이 유리할 수도 있다는 점에 유의하라. 그러나 복도를 따라 뒤쪽으로 가는 무빙워크는 없다.

점수

여러 테스트 케이스 그룹으로 풀이를 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$8$| $N,M \le 10$이고 뒤로 갈 필요가 전혀 없다.

$2$ |$13$| $N,M \le 1000$이고 뒤로 갈 필요가 전혀 없다.

$3$ |$40$| 뒤로 갈 필요가 전혀 없다.

$4$ |$15$| $N,M \le 1000$

$5$ |$24$| 추가 제한 없음.

입력의 첫 번째 줄에는 세 정수 $N, M$와 $g$가 주어진다 ($1 \le N \le 2 \cdot 10^5$, $2 \le M \le 2 \cdot 10^5$, $1 \le g \le 100$). 이는 무빙워크의 수, 복도의 길이(미터), 대표팀이 한 미터를 걷는 데 걸리는 시간(초)이다.

이어지는 $N$개의 줄에는 각각 무빙워크 하나를 설명하는 세 정수 $s_i, e_i$와 $t_i$가 주어진다 ($1\leq s_i < e_i\leq M,1\leq t_i\leq100$). 이는 복도 시작 지점부터 무빙워크 시작 지점까지의 거리(미터), 복도 시작 지점부터 무빙워크 끝 지점까지의 거리(미터), 무빙워크를 이용하는 데 걸리는 시간을 나타낸다.

대표팀이 경로를 최적으로 계획했을 때 복도 끝에 도달하는 데 걸리는 시간을 나타내는 정수를 출력한다.

예제 1

예제 1에서 대표팀이 무빙워크에 타고 있지 않을 때 한 미터를 걷는 데 2초가 걸린다. 복도 끝에 도달하는 가장 빠른 방법은 이용하는 데 5초가 걸리는 무빙워크까지 걸어가서 이를 이용한 뒤, 이용하는 데 2초가 걸리는 무빙워크까지 걸어가서 이를 이용하는 것이다. 총 $4+5+2+2=13$초가 걸린다.

예제 2

예제 2에서는 대표팀이 무빙워크에 타고 있지 않을 때 한 미터를 걷는 데 대신 5초가 걸린다. 복도 끝에 도달하는 가장 빠른 방법은 이용하는 데 8초가 걸리는 무빙워크까지 걸어가서 이를 이용한 다음, 한 미터 뒤로 가서 이용하는 데 2초가 걸리는 무빙워크를 이용하고, 마지막 한 미터를 걷는 것이다. 총 $5+8+5+2+5=25$초가 걸린다.