hzCPPOJ

香港记者(hkjournalist)

时间限制:  1 s      内存限制:   128 MB
提交:39     正确:6     分值:99

题目描述

“你们有一个好,全世界跑到什么地方,你们比其他的西方记者跑得还快。” 这是一位长者对香港记者ZY老师的称赞。现在香港记者ZY老师要和另一个西方记者YZ老师一起出发去报道新闻,新闻地点距离它们距离为L(1≤L≤106),ZY老师跑一个单位长度需要r(1≤ r≤ 106)秒的时间,YZ老师跑一个单位长度需要r(1≤ r≤ 106)秒的时间,由于ZY老师跑得快,所以< rF 。

YZ老师跑得太慢,所以不能休息,而ZY老师可以选择在一些特定的位置休息,一共有n(1≤n≤105个可供休息的位置,其中第i个位置距离起点x,在第i个位置休息t的时间可以获得Ci·t的愉悦值。

ZY老师不想侮辱香港记者的尊严,所以她任何时刻都不能落在西方记者YZ老师的后面,在此前提下,ZY老师希望最大化自己的愉悦值。

输入

第一行,四个整数L,n,F ,r,含义如题目描述。

接下来n行,每行两个整数xi,ci,含义如题目所述。

输出

一个整数,表示ZY老师可以获得的最大愉悦值。

样例

样例输入:
10 2 4 3 7 2 8 1
样例输出:
15

提示

ZY老师的最优方案是在x=7处休息7秒,获得14点愉悦值。

然后在x=8处休息1秒,获得1点愉悦值。

提交人

AmberXie

来源/分类