题目描述

sxz 和他的私人教练小江正在攀登温哥华山。为了他们的目的（以及你的目的），这座山可以表示为一条长度为 $L$ 米的长直步道 $（1≤L≤10^6）$。sxz 将以每米 $r_F$ 秒的恒定速度徒步 $（1≤r_F≤10^6）$。由于他正在锻炼耐力，他不会在途中休息。

然而，小江被允许在休息站休息，她可能会在那里找到一些美味的草。当然，她不能随便停下来！步道上有 $N$ 个休息站 $（1≤N≤10^5）$；第 $i$ 个休息站距离步道起点 $x_i$ 米 $（0<x_i<L）$，并且有一个美味值 $c_i$$（1≤c_i≤10^6）$。如果小江在第 $i$ 个休息站休息 $t$ 秒，她会获得 $c_i×t$ 的美味单位。当不在休息站时，小江将以每米 $r_B$ 秒的固定速度徒步$（1≤r_B≤10^6）$。由于小江年轻且健康，$r_B$ 严格小于 $r_F$。

小江希望最大化她摄入的美味草量。但她担心 sxz；她认为如果在徒步的任何时刻她在步道上落后于 sxz，他可能会失去继续前进的动力！

请帮助小江找到在确保 sxz 完成徒步的情况下，她能获得的最大总美味单位。

输入格式

输入的第一行包含四个整数：$L$、$N$、$r_F$ 和 $r_B$。接下来的 $N$ 行描述了休息站。对于每个 $i$ 从 $1$ 到 $N$，第 $i+1$ 行包含两个整数 $x_i$ 和 $c_i$，分别描述第$i$个休息站的位置和草的美味值。 保证 $r_F$>$r_B$，且 $0<x1<⋯<x_N<L$。注意，$r_F$ 和 $r_B$ 的单位是秒每米！

输出格式

输出一个整数：小江能获得的最大总美味单位。

样例 #1

样例输入 #1

10 2 4 3
7 2
8 1

样例输出 #1

15

提示

在这个例子中，小江最优的策略是在 $x=7$ 的休息站休息 $7$ 秒（获得 $14$ 个美味单位），然后在 $x=8$ 的休息站再休息 $1$ 秒（获得 $1$ 个美味单位，总共 $15$ 个美味单位）。

本题输入可参考下列方式实现：

l, n, v1, v2 = map(int, input().split())
a = []
for i in range(n):
    start, value = map(int, input().split())
    a.append([start, value])

来源

sxz