在一条细长的直线上，坐落着 JOI 理事长 K 的家和前理事长 M 的家。擅长跳跃的考拉 IOI 君计划从 K 理事长的家出发，前往 M 前理事长的家。

这条道路可以看作一条数轴，每个地点由一个坐标表示。K 理事长的家坐标为 $K$，M 前理事长的家坐标为 $M$。在这两者之间有 $N$ 个 JOI 导师的家，第 $i$ 个导师的家坐标为 $T_i$。

IOI 君以体力 0 从 K 理事长的家出发，通过多次跳跃前往 M 前理事长的家。每次跳跃可以向 M 前理事长的家方向前进距离 $d$，其中 $d$ 必须是满足 $1 \le d \le D$ 的整数。每进行一次跳跃，IOI 君的体力会减少 $A$（体力值可能为负数）。

如果 IOI 君跳跃到达的地点恰好有导师的家，他可以在该处停留一次。在第 $i$ 个导师的家停留时，IOI 君的体力会增加 $B_i$。

IOI 君希望在到达 M 前理事长的家时，体力值尽可能大。

题目描述

编写一个程序，求出考拉 IOI 君到达 M 前理事长的家时，体力值可能达到的最大值。

输入格式

从标准输入读取以下内容：

• 第 1 行包含 5 个整数 $K, M, D, A, N$，以空格分隔，分别表示 K 理事长的家坐标、M 前理事长的家坐标、单次跳跃的最大距离、单次跳跃减少的体力值以及导师家的数量。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含 2 个整数 $T_i, B_i$，以空格分隔，分别表示第 $i$ 个导师的家坐标以及在第 $i$ 个导师的家停留时增加的体力值。

输出格式

将考拉 IOI 君到达 M 前理事长的家时，体力值可能达到的最大值作为一个整数输出到标准输出。

数据范围

所有输入数据满足以下条件：

• $1 \le D \le 1\,000\,000\,000$
• $1 \le A \le 1\,000\,000\,000$
• $1 \le N \le 100\,000$
• $0 \le K < T_1 < \dots < T_N < M \le 1\,000\,000\,000$
• $1 \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$)

子任务

子任务 1 [20 分] * 满足 $N \le 1\,000$。

子任务 2 [30 分] * 满足 $D \le 100$。

子任务 3 [50 分] * 无附加限制。

样例

样例输入 1

0 10 4 10 2
3 10
8 5

样例输出 1

-20

说明 1

在此样例中，IOI 君的一种最优行动方案如下： 进行距离为 3 的跳跃。IOI 君到达坐标 3 的位置，体力变为 $-10$。 在第 1 个导师的家停留。体力变为 $0$。 进行距离为 4 的跳跃。IOI 君到达坐标 7 的位置，体力变为 $-10$。 进行距离为 3 的跳跃。IOI 君到达 M 前理事长的家，体力变为 $-20$。

样例输入 2

3 42 9 10 8
10 5
12 9
26 7
27 2
30 8
34 6
36 8
40 10

样例输出 2

-25

说明 2

在此样例中，IOI 君的一种最优行动方案如下： 进行距离为 9 的跳跃。IOI 君到达坐标 12 的位置，体力变为 $-10$。 在第 2 个导师的家停留。体力变为 $-1$。 进行距离为 9 的跳跃。IOI 君到达坐标 21 的位置，体力变为 $-11$。 进行距离为 9 的跳跃。IOI 君到达坐标 30 的位置，体力变为 $-21$。 在第 5 个导师的家停留。体力变为 $-13$。 进行距离为 6 的跳跃。IOI 君到达坐标 36 的位置，体力变为 $-23$。 在第 7 个导师的家停留。体力变为 $-15$。 进行距离为 6 的跳跃。IOI 君到达 M 前理事长的家，体力变为 $-25$。