Fuel Economy

A driver is setting out on a long road trip. The truck has a fuel tank that can hold at most $G$ units of fuel ($1 \le G \le 1{,}000{,}000$). The truck gets poor mileage: it burns exactly one unit of fuel for every unit of distance traveled, and the whole trip is $D$ units of distance long ($1 \le D \le 1{,}000{,}000{,}000$).

Because the tank may need to be refilled several times along the way, the driver lists all $N$ fuel stations on the route ($1 \le N \le 50{,}000$). Station $i$ sits at distance $X_i$ from the start ($0 \le X_i \le D$) and sells fuel at a price of $Y_i$ per unit ($1 \le Y_i \le 1{,}000{,}000$).

The truck begins the trip with exactly $B$ units of fuel already in the tank ($0 \le B \le D$). Determine the minimum total amount of money that must be spent on fuel to reach the destination at distance $D$. If reaching the destination is impossible, output $-1$ instead.

Note: the answer may not fit in a signed $32$-bit integer.

• Line $1$: four space-separated integers $N$, $G$, $B$, and $D$.
• Lines $2 \dots N+1$: line $i+1$ contains two integers $X_i$ and $Y_i$, the position and per-unit price of station $i$.

• One line: the minimum cost to reach the destination, or $-1$ if the destination cannot be reached.

In the first case the route runs from position $0$ to $D = 17$. The truck starts with $3$ units of fuel in a tank of capacity $10$, and there are $4$ stations.

One optimal plan: drive $2$ units to the station at position $2$ and buy $2$ units there (cost $40 \times 2$) to reach the station at position $5$; fill the tank completely there (cost $7 \times 10$); at position $10$ buy $2$ more units (cost $12 \times 2$). The total cost is $174$.

A greedy strategy works: at each station, if a cheaper station lies within one full tank's range, buy only enough fuel to reach it; otherwise fill the tank completely and continue to the cheapest reachable station.