Fueling the Journey

Farmer John has decided to take a cross-country vacation and bring his cows along in a large truck. The truck has a fuel tank that can hold up to \(G\) units of fuel (\(1 \le G \le 10^6\)), but it consumes one unit of fuel per unit distance traveled. FJ needs to travel a total distance of \(D\) (\(1 \le D \le 10^9\)).

To prepare for the trip, he has recorded the details of \(N\) fuel stations along his route (\(1 \le N \le 50000\)). For each station \(i\), he knows its distance from the start \(X_i\) (\(0 \le X_i \le D\)) and the price per unit fuel \(Y_i\) (\(1 \le Y_i \le 10^6\)).

Farmer John starts his journey with exactly \(B\) units of fuel (\(0 \le B \le D\)). Note that he cannot purchase fuel at the starting location. At each fuel station, he may choose to refuel, but his fuel tank cannot hold more than \(G\) units at any time. Determine the minimum amount of money FJ must spend on fuel in order to reach his destination. If it is impossible to reach the destination, output -1.

inputFormat

The input is given as follows:

The first line contains four integers (G), (D), (N), and (B), separated by spaces.

Each of the next (N) lines contains two integers (X_i) and (Y_i), representing the distance of the (i)th fuel station from the start and its price per unit fuel, respectively.

It is not guaranteed that the fuel station positions are given in sorted order.

outputFormat

Output a single integer on a line: the minimum cost required to reach the destination. If it is impossible to reach the destination, output -1.

sample

50 100 3 10
10 10
50 5
80 3

610