#U1718FS1. Rest Stops
Rest Stops
Farmer John和他的私人教练Bessie正在徒步攀登温哥牛山。基于他们的目的(也是你的目的),这座山可以用一条长为L米()的长直路径表示。Farmer John会沿着这条路径以每米rF秒()的固定速度攀登。由于他正在训练他的耐力,他在途中不会进行任何的休息。然而Bessie可以在休息站休息,在那里她能够找到一些美味的嫩草。当然,她也不能在任何地方都休息!在路径上总共有N个休息站();第i个休息站距离路径的起点米(<L),美味值为()。如果Bessie在休息站i休息了t秒,她能够得到个美味单位。
不在休息站的时候,Bessie会以每米秒()的固定速度攀登。由于Bessie年轻而健康,严格小于。
Bessie想要吃到最多的美味嫩草。然而她也担心Farmer John;她认为如果在任何时候她位于Farmer John身后,Farmer John可能就会失去前进的动力了!
帮助Bessie求出,在确保Farmer John能够完成登山的情况下,她能够获得的最多的美味单位。
输入格式(文件名:reststops.in):
输入的第一行包含四个整数:L,N,r,以及r。下面N行描述了休息站。对于1至N之间的每一个i,第i+1行包含了两个整数x和c,描述了第i个休息站的位置和那里的草的美味值。输入保证r>r,并且0<x<⋯<x<L。注意r和r的单位为秒每米!
输出格式(文件名:reststops.out):
输出一个整数:Bessie可以获得的最多的美味单位。
输入样例:
10 2 4 3
7 2
8 1
输出样例:
15
在这个样例中,Bessie的最佳方案是在位于x=7的休息站停留7秒(获得14个美味单位),再在位于x=8的休息站停留1秒(再获得1个美味单位,总共是15个美味单位)。