A21683.Rest Stops S

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Farmer John和他的私人教练Bessie正在徒步攀登温哥牛山。基于他们的目的(也是你的目的),这座山可以用一条长为LL米(1L1061 \leq L \leq 10^6)的长直路径表示。Farmer John会沿着这条路径以每米rFr_F秒(1rF1061 \leq r_F \leq 10^6)的固定速度攀登。由于他正在训练他的耐力,他在途中不会进行任何的休息。
然而Bessie可以在休息站休息,在那里她能够找到一些美味的嫩草。当然,她也不能在任何地方都休息!在路径上总共有NN个休息站(1N1051 \leq N \leq 10^5);第ii个休息站距离路径的起点xix_i米(0<xi<L0 < x_i < L),美味值为cic_i1ci1061 \leq c_i \leq 10^6)。如果Bessie在休息站ii休息了tt秒,她能够得到citc_i \cdot t个美味单位。

不在休息站的时候,Bessie会以每米rBr_B秒(1rB1061 \leq r_B \leq 10^6)的固定速度攀登。由于Bessie年轻而健康,rBr_B严格小于rFr_F

Bessie想要吃到最多的美味嫩草。然而她也担心Farmer John;她认为如果在任何时候她位于Farmer John身后,Farmer John可能就会失去前进的动力了!

帮助Bessie求出,在确保Farmer John能够完成登山的情况下,她能够获得的最多的美味单位。

输入格式

输入格式(文件名:reststops.in):
输入的第一行包含四个整数:LLNNrFr_F,以及rBr_B。下面NN行描述了休息站。对于11NN之间的每一个ii,第i+1i+1行包含了两个整数xix_icic_i,描述了第ii个休息站的位置和那里的草的美味值。
输入保证rF>rBr_F > r_B,并且0<x1<<xN<L0 < x_1 < \dots < x_N < L。注意rFr_FrBr_B的单位为秒每米!

输出格式

输出格式(文件名:reststops.out):
输出一个整数:Bessie可以获得的最多的美味单位。

输入输出样例

  • 输入#1

    10 2 4 3
    7 2
    8 1

    输出#1

    15
首页