연료비 최소화

한 운전자가 장거리 여행을 떠난다. 트럭의 연료 탱크는 최대 $G$ 단위의 연료를 담을 수 있다 ($1 \le G \le 1{,}000{,}000$). 이 트럭은 연비가 나빠서 이동 거리 $1$ 단위마다 연료를 정확히 $1$ 단위씩 소비하며, 전체 이동 거리는 $D$ 단위이다 ($1 \le D \le 1{,}000{,}000{,}000$).

이동 중 여러 번 주유해야 할 수 있으므로, 운전자는 경로상의 모든 주유소 $N$개를 조사했다 ($1 \le N \le 50{,}000$). $i$번째 주유소는 출발점에서 거리 $X_i$ 지점에 있으며 ($0 \le X_i \le D$), 연료를 단위당 $Y_i$의 가격에 판매한다 ($1 \le Y_i \le 1{,}000{,}000$).

트럭은 출발할 때 탱크에 정확히 $B$ 단위의 연료를 가지고 있다 ($0 \le B \le D$). 거리 $D$의 목적지에 도착하기 위해 연료비로 지불해야 하는 최소 금액을 구하여라. 목적지에 도착할 수 없다면 대신 $-1$을 출력한다.

참고: 정답은 부호 있는 $32$비트 정수 범위를 벗어날 수 있다.

• 첫째 줄: 공백으로 구분된 네 정수 $N$, $G$, $B$, $D$.
• $2$번째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 $i$번째 주유소의 위치와 단위당 가격을 나타내는 두 정수 $X_i$와 $Y_i$가 주어진다.

• 목적지에 도착하기 위한 최소 비용을 한 줄에 출력한다. 도착할 수 없다면 $-1$을 출력한다.

첫 번째 예시에서 경로는 위치 $0$에서 $D = 17$까지 이어진다. 트럭은 용량 $10$짜리 탱크에 $3$ 단위의 연료를 가지고 출발하며, 주유소는 $4$개이다.

최적의 한 가지 방법: 위치 $2$의 주유소까지 $2$만큼 이동한 뒤 그곳에서 $2$ 단위를 구매하고(비용 $40 \times 2$) 위치 $5$의 주유소에 도달한다. 그곳에서 탱크를 가득 채우고(비용 $7 \times 10$), 위치 $10$에서 $2$ 단위를 더 구매한다(비용 $12 \times 2$). 총 비용은 $174$이다.

탐욕적 전략이 유효하다: 각 주유소에서 탱크를 가득 채운 상태로 도달할 수 있는 범위 안에 더 싼 주유소가 있으면 그곳에 도달할 만큼만 구매하고, 없으면 탱크를 가득 채운 뒤 도달 가능한 가장 싼 주유소로 이동한다.