A2594. Rest Stops S
编程题
普及+/提高
知识点
题目描述
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能够完成登山的情况下,她能够获得的最多的美味单位。
然而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$的单位为秒每米!
输入的第一行包含四个整数:$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可以获得的最多的美味单位。
输出一个整数:Bessie可以获得的最多的美味单位。
输入输出样例
输入 #1
10 2 4 3 7 2 8 1
输出 #1
15