题目描述

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$ meters ($1 \leq L \leq 10^6$). Farmer John will hike the trail at a constant travel rate of $r_F$ seconds per meter ($1 \leq r_F \leq 10^6$). 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 might find some tasty grass. Of course, she cannot stop just anywhere! There are $N$ rest stops along the trail ($1 \leq N \leq 10^5$); the $i$-th stop is $x_i$ meters from the start of the trail ($0 < x_i < L$) and has a tastiness value $c_i$ ($1 \leq c_i \leq 10^6$). If Bessie rests at stop $i$ for $t$ seconds, she receives $c_i \cdot t$ tastiness units.

When not at a rest stop, Bessie will be hiking at a fixed travel rate of $r_B$ seconds per meter ($1 \leq r_B \leq 10^6$). Since Bessie is young and fit, $r_B$ is strictly less than $r_F$.

Bessie would like to maximize her consumption of tasty grass. But she is worried about Farmer John; she thinks that if at any point along the hike she is behind Farmer John on the trail, he might lose all motivation to continue!

Help Bessie find the maximum total tastiness units she can obtain while making sure that Farmer John completes the hike.

输入格式

The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest stop and the tastiness of the grass there. It is guaranteed that $r_F > r_B$, and $0 < x_1 < \dots < x_N < L$. Note that $r_F$ and $r_B$ are given in seconds per meter!

输出格式

A single integer: the maximum total tastiness units Bessie can obtain.

题目大意

Farmer John和他的私人教练Bessie正在徒步攀登温哥牛山。基于他们的目的（也是你的目的），这座山可以用一条长为$L$米（$1 \leq L \leq 10^6$）的长直路径表示。Farmer John会沿着这条路径以每米$r_F$秒（$1 \leq r_F \leq 10^6$）的固定速度攀登。由于他正在训练他的耐力，他在途中不会进行任何的休息。 然而Bessie可以在休息站休息，在那里她能够找到一些美味的嫩草。当然，她也不能在任何地方都休息！在路径上总共有$N$个休息站（$1 \leq N \leq 10^5$）；第$i$个休息站距离路径的起点$x_i$米（$0 < x_i < L$），美味值为$c_i$（$1 \leq c_i \leq 10^6$）。如果Bessie在休息站$i$休息了$t$秒，她能够得到$c_i \cdot t$个美味单位。

不在休息站的时候，Bessie会以每米$r_B$秒（$1 \leq r_B \leq 10^6$）的固定速度攀登。由于Bessie年轻而健康，$r_B$严格小于$r_F$。

Bessie想要吃到最多的美味嫩草。然而她也担心Farmer John；她认为如果在任何时候她位于Farmer John身后，Farmer John可能就会失去前进的动力了！

帮助Bessie求出，在确保Farmer John能够完成登山的情况下，她能够获得的最多的美味单位。

输入格式（文件名：reststops.in）： 输入的第一行包含四个整数：$L$，$N$，$r_F$，以及$r_B$。下面$N$行描述了休息站。对于$1$至$N$之间的每一个$i$，第$i+1$行包含了两个整数$x_i$和$c_i$，描述了第$i$个休息站的位置和那里的草的美味值。 输入保证$r_F > r_B$，并且$0 < x_1 < \dots < x_N < L$。注意$r_F$和$r_B$的单位为秒每米！

输出格式（文件名：reststops.out）： 输出一个整数：Bessie可以获得的最多的美味单位。

10 2 4 3
7 2
8 1

15

提示

In this example, it is optimal for Bessie to stop for $7$ seconds at the $x=7$ rest stop (acquiring $14$ tastiness units) and then stop for an additional $1$ second at the $x=8$ rest stop (acquiring $1$ more tastiness unit, for a total of $15$ tastiness units).

Problem credits: Dhruv Rohatgi