题目

题目描述

wyh8000很喜欢看书, 特别是那种很容易死脑细胞的书。

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

好心的学长不希望看到wyh8000的脑细胞死光，你能帮助wyh8000死掉尽可能少的脑细胞吗？

输入格式

第一行五个非负整数$K,M,D,A,N$。

$K,M,D,A$如题目描述。$N$表示有$N$页wyh8000比较感兴趣。

接下来$N$行，每一行两个正整数，$T_i,B_i$，表示当wyh8000阅读第$T_i$页时，能回复$B_i$的脑细胞。

输出格式

一个整数$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$。

数据范围

对于全部数据，$1\le B_i,A,D\le 10^9$，$1\le N\le 10^5$。$0\le K<T_1<T_2<\dots<T_N<M\le 10^9$。

对于$20\%$数据，$N\le 1000$；

对于另$30\%$数据，$D\le 100$。