P14439 [JOISC 2013] 考拉 / Koala

在一条细长的直线道路上，有 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 前理事长的家时可能的最大体力值。

从标准输入读取以下输入数据： - 第 $1$ 行包含以空格分隔的整数 $K, M, D, A, N$，分别表示 K 理事长的家坐标、M 前理事长的家坐标、单次跳跃的最大距离、单次跳跃消耗的体力、导师家的数量。 - 后续 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含以空格分隔的两个整数 $T_i, B_i$，分别表示第 $i$ 个导师家的坐标、在第 $i$ 个导师家住宿时增加的体力值。

向标准输出输出一个整数，表示 IOI 君到达 M 前理事长的家时可能的最大体力值。

### 样例 1 解释 在此示例中，IOI 君的最优行动方案如下： - 进行距离为 $3$ 的跳跃。IOI 君到达坐标 $3$ 的位置，体力变为 $-10$。 - 在第 $1$ 个导师家住宿。体力变为 $0$。 - 进行距离为 $4$ 的跳跃。IOI 君到达坐标 $7$ 的位置，体力变为 $-10$。 - 进行距离为 $3$ 的跳跃。IOI 君到达 M 前理事长的家，体力变为 $-20$。 ### 样例 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$。 ### 限制 所有输入数据满足以下条件： - $1 \leq D \leq 1\,000\,000\,000$ - $1 \leq A \leq 1\,000\,000\,000$ - $1 \leq N \leq 100\,000$ - $0 \leq K < T_1 < \cdots < T_N < M \leq 1\,000\,000\,000$ - $1 \leq B_i \leq 1\,000\,000\,000$ ($1 \leq i \leq N$) --- ### 子任务 #### 子任务 1 [20 分] - 满足 $N \leq 1\,000$ #### 子任务 2 [30 分] - 满足 $D \leq 100$ #### 子任务 3 [50 分] 无额外限制 翻译由 DeepSeek V3 完成