트럭 여행

찬진은 큰 트럭을 렌트해서 대륙 횡단 여행을 하기로 결심했습니다!

트럭은 G 단위의 연료를 가지고 있습니다 (1 <= G <= 1,000,000). 불행히도 트럭은 연비가 좋지않습니다: 

트럭은 여행한 거리 단위마다 연료 한 단위를 소비하고, 찬진은 경로를 따라 이동할 수 있는 총 D 단위의 거리를 가지고 있습니다 (1 <= D <= 1,000,000,000).

여행 동안 트럭의 탱크를 여러 번 채우기 위해 멈추어야 하기 때문에, 찬진은 경로를 따라 있는 모든 N 개의 주유소를 모두 목록으로 만듭니다 (1 <= N <= 50,000). 각각의 주유소 i에 대해, 그는 그의 루트의 시작부터 X_i라는 거리를 기록하며, 판매하는 연료의 단위당 가격 Y_i를 기록합니다 (1 <= Y_i <= 1,000,000).

이 정보와 찬진이 그의 여행을 정확히 B 단위의 연료로 시작한다는 사실 (0 <= B <= D)을 고려하여, 찬진이 목적지에 도달하기 위해 연료를 위해 지불해야 할 최소한의 돈을 결정해 주십시오. 그것이 그의 목적지에 도달하는 것이 불가능하다면, -1을 출력하십시오. 이 문제의 대답이 표준 32비트 정수에 들어갈 수 없을 수도 있음을 알려주십시오.

• 첫 번째 줄 : 네 개의 공백으로 구분된 정수: N, G, B, D.
• 두 번째 줄..1+N 번째 줄 : 각 줄은 i번째 주유소를 설명하는 두 개의 정수 X_i와 Y_i를 포함합니다.

• 첫 번째 줄 : 찬진이 목적지에 도달하기 위해 지불해야 하는 최소 비용, 또는 찬진이 목적지에 도달하는 것이 불가능하다면 -1.