行星探测车 Tycho VIII 在收集完矿物样本后需要返回基地。Tycho 在一条直线上从位置 $0$ 行进至位于位置 $b$ 的基地。在移动过程中，它以每秒 $1$ 个单位的恒定慢速前进。每过一秒，Tycho 都会因恶劣的行星环境受到 $1$ 个单位的伤害。
附近脉冲星产生的辐射使情况变得更糟，每过 $p$ 秒就会额外造成 $d$ 个单位的伤害。然而，通过在沿途的 $n$ 个不同藏身处（洞穴、植被、巨石、行星巨型动物的尸体）中寻求庇护，可以避免辐射伤害。Tycho 可以选择在任何位置原地停留任意整数秒。
起点 $0$ 和基地 $b$ 都是受庇护的，因此 Tycho 在这些位置不会受到辐射伤害。
Tycho 在返回基地的旅程中受到的最小伤害是多少？
输入格式
第一行包含四个整数 $b, p, d, n$，由空格分隔：基地位置 $b$，脉冲星耀斑周期 $p$，每次脉冲星耀斑造成的额外辐射伤害 $d$，以及藏身处数量 $n$。 接下来的 $n$ 行，每行包含一个整数，表示藏身处的位置 $a_1, \dots, a_n$，满足 $0 < a_1 < \dots < a_n < b$。
输出格式
输出一个整数：Tycho 到达 $b$ 所需承受的最小伤害总量。
约束条件与评分
你可以假设 $p < b$ 且 $n < b$。始终满足 $1 \le b \le 10^{12}$，$0 \le d \le 10^6$，$0 \le n \le 10^5$。
你的解决方案将在多组测试数据上进行测试，每组测试数据包含若干测试点。要获得某一组的分数，你需要通过该组内的所有测试点。最终得分为单次提交的最高得分。
| 组别 | 分数 | 约束条件 |
|---|---|---|
| 1 | 8 | $p \le 10^6$ 且 Tycho 在离开位置 $0$ 后无需等待。* |
| 2 | 5 | $b \le 1000, p \le 100, n \le 10$ |
| 3 | 7 | $b \le 1000$ |
| 4 | 15 | $p \le 10^6, n \le 1000$ |
| 5 | 20 | $p \le 100$ |
| 6 | 35 | $p \le 10^6$ |
| 7 | 10 | 无额外约束 |
- 在测试组 1 中，Tycho 在开始移动前可能仍需要在位置 $0$ 等待。例如，样例输入 2、3 和 4 属于测试组 1。
样例
输入格式 1
18 4 5 2 8 15
输出格式 1
29
输入格式 2
18 4 0 2 8 15
输出格式 2
18
输入格式 3
18 10 100 2 8 15
输出格式 3
20
输入格式 4
18 4 100 0
输出格式 4
418
输入格式 5
65 20 100 3 14 25 33
输出格式 5
172