Rest Stops#10408
Farmer John and his personal trainer Bessie are hiking up Mount Vancowver. For their purposes (and yours), the mountain can be represented as a long straight trail of length l~(1 \le l \le 10^6) meters. Farmer John will hike the trail at a constant pace of r_F~(1 \le r_F \le 10^6) seconds per meter. Since he is working on his stamina, he will not take any rest stops along the way.
Bessie, however, is allowed to take rest stops, where she may find some tasty grass. Of course, she cannot stop just anywhere! There are n~(1 \le n \le 10^5) rest stops along the trail; the -th stop is located x_i~(0 < x_i < l) meters from the start of the trail and has a tastiness value c_i~(1 \le c_i \le 10^6). If Bessie rests at stop for seconds, she receives c_i \cdot t tastiness units.
When not at a rest stop, Bessie hikes at a constant pace of r_B~(1 \le r_B \le 10^6) seconds per meter. Since Bessie is young and fit, r_B is strictly less than r_F.
Bessie would like to eat as much tasty grass as possible. However, she is worried about Farmer John: she believes that if at any moment during the hike she falls behind him on the trail, he might lose all motivation to continue!
Help Bessie find the maximum total number of tastiness units she can obtain while making sure that Farmer John completes the hike.
The first line contains four integers l, n, r_F and r_B. The next lines describe the rest stops: the (i + 1)-th line contains two integers x_i and c_i — the position of the -th rest stop and the tastiness of the grass there.
It is guaranteed that r_F > r_B and 0 < x_1 < \ldots < x_n < l. Note that r_F and r_B are given in seconds per meter!
Print one integer — the maximum total number of tastiness units Bessie can obtain.
Example 1
In this example, it is optimal for Bessie to stop for seconds at the rest stop at x = 7 (receiving tastiness units) and then for another second at the rest stop at x = 8 (receiving more tastiness unit), for a total of tastiness units.