样例下载

题目描述

龟兔赛跑又开始了。

笔直的赛道长度为 $L$ 米，乌龟和兔子前进时均保持匀速，乌龟每前进一米需要花费的时间为 $T$ 秒，兔子每前进一米需要花费的时间为 $R$ 秒。自然，$R < T$。

乌龟依然保持着上一次比赛的坚持精神，全程不会停下脚步。

但是兔子发现赛道沿途分布着 $N$ 棵树，它希望途中可以选择一些树，当它到达树下时，可以美美地睡一觉。已知，第 $i$ 课树距离赛道起点的距离为 $X_i$ 米，在这棵树下每睡一秒，将会获得 $P_i$ 的愉悦值。

当然，吸取了上次赛跑失败的教训，兔子这次可不敢大意了。它准备好了闹钟，保证自己不会睡过头。并且，兔子只会选择在树下睡觉。当它到达一棵树下后，如果它选择在此睡一觉，则立刻就能睡着，闹钟响了立刻就会启程，全程只有前进和睡觉花费时间，其他如定闹钟、关闹钟等花费的时间全部忽略不计。而且，兔子希望全程不会被乌龟超越。

问：兔子如何安排自己在哪些树下睡觉以及睡觉时间，可以使得自己在全程不会被乌龟超越的前提下，获得的愉悦值之和最大？你只需要输出这个最大值。

输入

第一行：四个整数 $L, N, T, R$。

接下来 $N$ 行：每行两个整数 $X_i, P_i$。

数据保证 $R < T$，$0 < X_1 < X_2 < … < X_N < L$。

输出

一个整数，表示答案。

输入样例

8 2 5 4
4 2
6 1

输出样例

10

样例解释

到达第 1 棵树（$X_1=4$），花费 4×4=16 秒，兔子选择在此睡觉 4 秒，获得 2×4=8 的愉悦值。到了第 20 秒，乌龟到达第一棵树，此时兔子立刻启程，再花费 4×2=8 秒，到达第 2 棵树（$X_2=6$），选择在此睡觉 2 秒，获得 1×2=2 的愉悦值，此时乌龟到达第 2 棵树，兔子立刻启程，直至到达终点。总计获得 8+2=10 的愉悦值。

数据范围

一部分数据：$1 ≤ N ≤ 10^3$

一部分数据：$1 ≤ N ≤ 10^5$

全部数据：$1 ≤ N ≤ 2 × 10^7$, $1 ≤ L ≤ 10^6$, $0 < X_1 < X_2 < … < X_N < L$, $1 ≤ P_i ≤ 10^6$, $1 ≤ R < T ≤ 10^6$