충전 구간의 최소 비용

문제

전기차 한 대가 일직선 도로를 위치 0에서 위치 L까지 달린다. 배터리 용량은 B이고, 거리 1을 이동할 때마다 에너지가 정확히 1 소모된다. 출발할 때 배터리는 가득(에너지 B) 차 있으며, 이 처음 에너지는 비용이 들지 않는다. 도로 위의 서로 다른 위치 x_i에 충전소가 N개 있고, i번 충전소에서는 에너지 1당 p_i원에 충전할 수 있다. 충전은 정수 단위로만 할 수 있고, 한 충전소에서 원하는 만큼 충전할 수 있지만 배터리의 에너지는 언제나 B를 넘을 수 없다. 이동 중에 에너지가 0 아래로 내려가서는 안 되며, 에너지가 정확히 0인 상태로 충전소나 목적지에 도착하는 것은 허용된다. 목적지에 도착했을 때 남은 에너지는 버려진다. 충전소는 위치 순서와 무관하게 임의의 순서로 주어진다. 위치 L에 도착하기 위해 지불해야 하는 총 충전 비용의 최솟값을 구하시오. 어떻게 해도 도착할 수 없다면 -1을 출력한다.

입력

첫 줄에 정수 N, L, B가 공백으로 구분되어 주어진다. (0 ≤ N ≤ 200,000, 1 ≤ B ≤ L ≤ 10^9) 이어서 N개의 줄에 각각 정수 x_i, p_i가 주어진다. (1 ≤ x_i < L, 1 ≤ p_i ≤ 10^9, x_i는 모두 서로 다르다)

출력

최소 총 충전 비용을 한 줄에 출력한다. 도착할 수 없으면 -1을 출력한다.

3 10 4
3 5
6 2
8 9

18

1 10 4
6 1

-1

0 4 4

0

출처: Devin.KR 자체 제작