题目描述

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

0 10 4 10 2
3 10
8 5

-20

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

-25

提示

样例 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 完成