룰벤드

스웨덴 국제정보올림피아드 대표팀이 IOI 2020에 참가하기 위해 싱가포르에 막 도착했다. 수하물 찾는 곳으로 가는 길에 팀은 여러 개의 룰벤드(움직이는 보도)가 있는 긴 복도를 지나야 한다. 복도의 길이는 $M$미터이고, 팀은 지금 복도의 시작점에 서서 수하물 찾는 곳까지 얼마나 빨리 갈 수 있을지 고민하고 있다. 복도에는 $N$개의 룰벤드가 있다. 각 룰벤드는 복도 시작점으로부터 특정 거리에서 시작해 특정 거리에서 끝나며, 그 위를 이동하는 데 특정 시간이 걸린다. 모든 룰벤드는 복도 방향으로 움직이고, 룰벤드의 시작점에서만 탑승할 수 있으며 끝점에서만 내릴 수 있다. 팀이 룰벤드 위에 있지 않을 때 1미터를 걷는 데 $g$초가 걸린다. 복도와 룰벤드는 매우 좁아서 복도와 나란히 걷는 데 걸리는 시간만 중요하다. 즉, 어떤 룰벤드가 시작점으로부터의 거리에서 끝나고 다른 룰벤드가 같은 거리에서 시작하면 두 룰벤드 사이를 이동하는 데 시간이 걸리지 않는다. 팀이 복도 전체를 통과하는 데 걸리는 최단 시간은 얼마인가?

때로는 복도를 조금 뒤로 걸어가서 팀을 멀리 데려다주는 룰벤드에 타는 것이 유리할 수 있다. 하지만 복도를 뒤로 가는 룰벤드는 없다.

첫 번째 줄에는 세 정수 $N$, $M$, $g$가 주어진다 ($1 \le N \le 2\times10^5$, $2 \le M \le 2\times10^5$, $1 \le g \le 100$). $N$은 룰벤드의 개수, $M$은 복도의 길이(미터), $g$는 팀이 룰벤드 위에 있지 않을 때 1미터를 걷는 데 걸리는 시간(초)이다. 다음 $N$개의 줄은 룰벤드를 나타내며 각각 3개의 정수 $s\_i, e\_i, t\_i$를 포함한다 ($1\leq s\_i < e\_i\leq M,1\leq t\_i\leq100$). $s\_i$는 복도 시작점으로부터 룰벤드 시작점까지의 거리(미터), $e\_i$는 복도 시작점으로부터 룰벤드 끝점까지의 거리(미터), $t\_i$는 룰벤드 위를 이동하는 데 걸리는 시간(초)이다.

팀이 복도를 통과하는 데 걸리는 시간(초)을 나타내는 정수 하나를 한 줄에 출력한다.

그림 1: 예제 1

예제 1에서 팀이 룰벤드 위에 있지 않을 때 1미터를 걷는 데 2초가 걸린다. 끝까지 가는 가장 빠른 방법은 5초가 걸리는 룰벤드로 걸어가서 타고, 2초가 걸리는 룰벤드로 걸어가서 타는 것이다. 이때 걸리는 총 시간은 $4+5+2+2=13$초이다.

그림 2: 예제 2

예제 2에서는 팀이 룰벤드 위에 있지 않을 때 1미터를 걷는 데 5초가 걸린다. 끝까지 가는 가장 빠른 방법은 8초가 걸리는 룰벤드로 걸어가서 타고, 1미터 뒤로 걸어가서 2초가 걸리는 룰벤드에 타고, 마지막 1미터를 걷는 것이다. 이때 걸리는 총 시간은 $5+8+5+2+5=25$초이다.