UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4658. rescue

统计 下载数据

Description

wyh8000很喜欢看书,特别是那种很容易死脑细胞的书。
wyh8000看书喜欢从第K页开始看起,然后看到第M页,但是wvh8000并不是有耐心的小盆友,他
只想快点完成看书任务,然后就可以去愉快的农别人了,于是他经常跳着看,但是他一次最多跳D页,
然后阅读那一页的内容,然后死掉A的脑细胞。当然如果那一页的内容他比较感兴趣,又会回复一定
的脑细胞。
好心的学长不希望看到wyh8000的脑细胞死光,你能帮助wvh8000死掉尽可能少的脑细胞吗?

Input

第一行五个非负整数K,M,D,A,N。
K,M,D,A如题目描述。N表示有N页wvh8000比较感兴趣。
接下来N行,每一行两个正整数,Ti,Bi。,表示当wvh8000阅读第Ti页时,能回复Bi的脑细胞。
l <= Bi,A,D≤10^9,l<N<105。0<=K<T1<T2<…<Tn<M <= 10^9。

Output

一个整数ans。表示能拯救的最多的脑细胞数,若最后还是损失则为负数。

Sample Input

0 10 4 10 2
3 10
8 5

Sample Output

-20
wyh8000从第0页开始看。
wyh8000跳到第3页,损失10脑细胞。
wyh8000阅读第3页,拯救10脑细胞。
wyh8000跳到第7页并阅读,损失10脑细胞。
wyh8000眺到第10页并阅读,损失10脑细胞。
学长最后无能为力,但是损失20是最优的策略,所以输出为-20。

Hint

Source