题目描述

题目译自 JOISC 2013 Day3 T2 「コアラ」

在一条细长的直线道路上，有 JOI 的 K 理事长的家和 M 前理事长的家。擅长跳跃的考拉 IOI 君计划从 K 理事长的家前往 M 前理事长的家。

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

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

如果 IOI 君跳跃后落在一个导师的家所在的坐标，他可以在这家住一晚，且仅限一次。第 $i$ 个导师的家住宿后，IOI 君的体力增加 $B_{i}$。

IOI 君希望以尽可能多的体力到达 M 前理事长的家。

你需要编写一个程序，计算考拉 IOI 君到达 M 前理事长的家时可能拥有的最大体力值。

输入格式

从标准输入中读取以下数据：

• 第一行包含五个整数 $K, M, D, A, N$，用空格分隔，分别表示 K 理事长的家坐标、M 前理事长的家坐标、一次跳跃的最大距离、一次跳跃减少的体力值、导师家的数量。
• 接下来 $N$ 行中，第 $i$ $(1 \leq i \leq N)$ 行包含两个整数 $T_{i}, B_{i}$，用空格分隔，分别表示第 $i$ 个导师的家坐标和在该家住宿后增加的体力值。

输出格式

在标准输出中输出一行一个整数，表示考拉 IOI 君到达 M 前理事长的家时可能拥有的最大体力值。

0 10 4 10 2
3 10
8 5

-20

在此示例中，IOI 君的最佳行动方式如下：

• 跳跃距离 $3$，到达坐标 $3$，体力变为 $-10$。
• 在第 $1$ 个导师的家住宿，体力变为 $0$。
• 跳跃距离 $4$，到达坐标 $7$，体力变为 $-10$。
• 跳跃距离 $3$，到达 M 前理事长的家，体力变为 $-20$。

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

-25

在此示例中，IOI 君的最佳行动方式如下：

• 跳跃距离 $9$，到达坐标 $12$，体力变为 $-10$。
• 在第 $2$ 个导师的家住宿，体力变为 $-1$。
• 跳跃距离 $9$，到达坐标 $21$，体力变为 $-11$。
• 跳跃距离 $9$，到达坐标 $30$，体力变为 $-21$。
• 在第 $5$ 个导师的家住宿，体力变为 $-13$。
• 跳跃距离 $6$，到达坐标 $36$，体力变为 $-23$。
• 在第 $7$ 个导师的家住宿，体力变为 $-15$。
• 跳跃距离 $6$，到达 M 前理事长的家，体力变为 $-25$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq D \leq 1000000000$
• $1 \leq A \leq 1000000000$
• $1 \leq N \leq 100000$
• $0 \leq K < T_{1} < \cdots < T_{N} < M \leq 1000000000$
• $1 \leq B_{i} \leq 1000000000$ $(1 \leq i \leq N)$

详细子任务附加限制及分值如下表所示。