P6934: 休息站
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
Farmer John
和他的私人教练Bessie正在徒步攀登温哥牛山。基于他们的目的（也是你的目的），这座山可以用一条长为L
米（1≤L≤10
^6
）的长直路径表示。Farmer John
会沿着这条路径以rF秒每米（1≤rF≤10
^6
）的固定速度攀登。由于他正在训练他的耐力，他在途中不会进行任何的休息。
然而Bessie
可以在休息站休息，在那里她能够找到一些美味的嫩草。当然，她也不能在任何地方都休息！在路径上总共有N个休息站（1≤N≤10
^5
）；第i
个休息站距离路径的起点xi
米（0<xi<L
），美味值为ci
（1≤ci≤10
^6
）。如果Bessie
在休息站i休息了t
秒，她能够得到ci×t
个美味单位。
不在休息站的时候，Bessie
会以rB秒每米（1≤rB≤10
^6
）的固定速度攀登。由于Bessie
年轻而健康，rB严格小于rF
。
Bessie
想要吃到最多的美味嫩草。然而她也担心Farmer John；她认为如果在任何时候她位于Farmer John身后，Farmer John可能就会失去前进的动力了！
帮助Bessie
求出，在确保Farmer John能够完成登山的情况下，她能够获得的最多的美味单位。
【
输入格式】
（reststops.in
）：
输入的第一行包含四个整数：L
，N
，rF
，以及rB
。下面N
行描述了休息站。对于1
至N
之间的每一个i
，第i+1
行包含了两个整数xi
和ci
，描述了第i
个休息站的位置和那里的草的美味值。
输入保证rF>rB
，并且L0<x1<⋯<xN<L
。注意rF
和rB
的单位为秒每米！
【
输出格式】
（reststops.out
）：
输出一个整数：Bessie
可以获得的最多的美味单位。
【
输入样例】
：
10 2 4 3
7 2
8 1
【
输出样例】
：
15
【样例说明】
在这个样例中，Bessie
的最佳方案是在位于x=7的休息站停留7
秒（获得14
个美味单位），再在位于x=8
的休息站停留1
秒（再获得1
个美味单位，总共是15
个美味单位）。