美味
时间限制:1秒 内存限制:256M
【题目描述】
小H正在大H的带领下练习跑步。跑步的路线是一条长为 \(L\) 米的直路表示。
小H会沿着这条路线以每米 \(F\) 秒的固定速度前进。由于他正在训练自己的耐力,他在途中不会进行任何片刻的休息。然而大H可以在沿途的驿站休息,在那里他能够找到一些可口的美食。当然,他也不能在任何地方都休息!
在路线上总共有 \(N\) 个驿站;第 \(i\) 个小吃店距离路线的起点 \(x_i\),美味值为 \(c_i\)。如果大H在小吃店 \(i\) 休息了 \(t\) 秒,他能够得 \(c_i*t\) 个美味单位。
不在驿站的时候,大H会以每米 \(B\) 秒的固定速度前进。由于大H身强力壮,所以 \(B\) 严格小于 \(F\)。
大H想要享受更多的美味,然而他也担心小H;他认为如果在任何时候位于小H身后,小H可能就会失去前进的动力了!请帮助大H求出,在确保小H能够完成跑步的情况下,他能够获得的最多的美味单位。
【输入格式】
输入的第一行包含四个整数:\(L,N,F\) 以及 \(B\)。
下面 \(N\) 行描述了小吃店。对于 1 至 \(N\) 之间的每一个 \(i\),第 \(i+1\) 行包含了两个整数 \(x_i\) 和 \(c_i\),描述了第 \(i\) 个小吃店的位置和那里的草的美味值。
输入保证 \(B<F\),并且 \(0<x_1<⋯<x_N<L\)。注意 \(F\)和 \(B\) 的单位为秒每米!
【输出格式】
最大美味值。
【输入输出样例】
Input
10 2 4 3
7 2
8 1
Output
15
【数据限制】
对于 \(100\%\) 的数据,\(1≤L≤10^6\),\(1≤N≤10^5\),\(1≤B<F≤10^6\)
【来源】
Mr.he