8658: BZOJ4658：rescue

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

输入格式

第一行五个非负整数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。

输出格式

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

样例输入

0 10 4 10 2
3 10
8 5

样例输出

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

提示

没有写明提示

题目来源

没有写明来源