교환식 충전소 경로

문제

전기차 한 대가 일직선 도로의 출발 지점 0에서 도착 지점 D까지 달린다. 도로 위 0과 D 사이에는 배터리 교환식 충전소가 N개 있다. i번째 충전소는 위치 x_i에 있고, 이용할 때마다 요금 c_i를 내며, 이용하면 배터리를 통째로 갈아 끼워 그 자리에서 앞쪽으로 정확히 L_i만큼 달릴 수 있는 새 배터리를 얻는다. 즉 위치 x_i에서 교체했다면 위치 x_i+L_i 이하의 지점까지 갈 수 있고, 이전 배터리에 남은 거리는 모두 버려진다. 전기차는 출발할 때 이미 거리 S짜리 배터리를 달고 있어 위치 S 이하까지 달릴 수 있으며, 이 배터리에는 요금이 들지 않는다. 전기차는 앞으로만 움직이고, 현재 배터리로 닿을 수 있는 위치에 있는 충전소에서만 멈춰 배터리를 교체할 수 있다. 한 번 교체한 뒤 닿을 수 있는 충전소 중 어느 것을 다음에 이용할지는 자유이다. 같은 충전소를 두 번 이용하는 일은 없으며, 충전소의 위치는 모두 다르고 입력 순서는 위치 순서와 무관하다. 도착 지점 D까지 가는 데 쓴 충전소 요금의 합을 최소로 만들고 싶다. 충전소를 하나도 쓰지 않고 도착할 수 있으면 0이다. 도착 지점에 도달하는 방법이 없으면 -1을 출력한다. 요금의 합은 32비트 정수 범위를 넘을 수 있다.

입력

첫 줄에 정수 N, D, S가 공백으로 구분되어 주어진다. 이어지는 N개의 줄에 i번째 충전소의 x_i, L_i, c_i가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 2 ≤ D ≤ 10^9, 1 ≤ S ≤ D, 1 ≤ x_i ≤ D-1이며 x_i는 서로 다르다. 1 ≤ L_i ≤ D, 0 ≤ c_i ≤ 10^9이다. 모든 값은 정수이다.

출력

도착 지점에 도달하는 데 드는 요금 합의 최솟값을 한 줄에 출력한다. 도달할 수 없으면 -1을 출력한다.

4 10 4
3 5 7
4 2 2
6 4 3
8 3 5

5

2 10 3
2 2 1
8 1 1

-1

1 5 5
2 1 100

0

출처: Devin.KR 자체 제작