Rest Stops

Farmer John is hiking a mountain trail of length \(L\) meters at a constant pace of \(r_F\) seconds per meter. His companion, Bessie, hikes faster (at \(r_B\) seconds per meter with \(r_B < r_F\)) and can take rest stops along the way. There are \(N\) rest stops along the trail. The \(i\)th rest stop is located at \(x_i\) meters from the start and has a tastiness value \(c_i\). If Bessie rests for \(t\) seconds at a stop, she gains \(c_i \cdot t\) tastiness units.

Bessie must never fall behind Farmer John; that is, at every point in time, her progress along the trail must be at least that of Farmer John. Because Bessie travels faster, she can accumulate waiting time. When she reaches a rest stop, the available waiting time (in seconds) is the difference between Farmer John's travel time and her own travel time from the previous stop (or the start) to the current stop. Formally, if Bessie travels from a previous position \(p_{prev}\) to a rest stop at \(x_i\), her extra time is \((x_i - p_{prev})\,(r_F - r_B)\) seconds.

To maximize total tastiness, Bessie should plan to rest only at select stops. In particular, if a stop has a tastiness value that is less than the maximum tastiness of any later stop, it is not optimal to rest there – Bessie is better off saving her waiting time for the later, tastier stop. The optimal strategy is to only rest at stops that are locally optimal, meaning that its tastiness value is equal to the maximum tastiness among all stops from that point to the end of the trail.

The task is to compute the maximum total tastiness units Bessie can obtain if she follows an optimal strategy while ensuring that Farmer John completes the hike.

The key observation is to precompute, for each rest stop, the maximum tastiness value among all stops from that stop to the end. Then, Bessie only rests at a stop if its tastiness equals that maximum. For each such stop, she waits for all the time she can (given by the distance traversed since her last rest stop multiplied by \(r_F - r_B\)) and collects tastiness units accordingly.

Input Note: The input begins with four space‐separated integers \(L, N, r_F, r_B\) followed by \(N\) lines each containing two space‐separated integers \(x_i\) and \(c_i\).

inputFormat

The first line of input contains four integers:

• \(L\) (\(1 \le L \le 10^6\)) – the length of the trail in meters.
• \(N\) (\(1 \le N \le 10^5\)) – the number of rest stops.
• \(r_F\) (\(1 \le r_F \le 10^6\)) – Farmer John's travel time per meter in seconds.
• \(r_B\) (\(1 \le r_B < r_F \le 10^6\)) – Bessie's travel time per meter in seconds.

Each of the next \(N\) lines contains two integers \(x_i\) and \(c_i\):

• \(x_i\) (\(0 < x_i < L\)) is the position of the rest stop in meters.
• \(c_i\) (\(1 \le c_i \le 10^6\)) is the tastiness value at that rest stop.

The rest stops are not necessarily given in sorted order.

outputFormat

Output a single integer: the maximum total tastiness units Bessie can obtain following an optimal strategy while ensuring she never falls behind Farmer John.

sample

10 2 4 3
7 2
8 1

15