/ Vijos / 题库 /

美味

美味

时间限制: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

信息

ID
2223
难度
(无)
分类
贪心 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
3
上传者