4188. 「BalticOI 2023」Tycho

题目描述

题目译自 BalticOI 2023 Day1「Tycho」

行星探测车 Tycho VIII 需要在采集完矿物样本后返回基地。探测车从位置 $0$ 沿直线行进，到达位于位置 $b$ 的基地。在移动过程中，它以每秒 $1$ 个单位的速度缓慢而稳定地前进。在恶劣的行星环境中，探测车每秒会受到 $1$ 单位的环境伤害。

附近一颗脉冲星的辐射使情况变得更糟，每 $p$ 秒就会再带来 $d$ 单位的附加伤害。不过，只要在沿途的 $n$ 个不同的藏身点（洞穴、植被、大岩石、行星上巨型动物的尸体）中找到一个，就能避免辐射伤害。探测车可以选择在任意点停留任意整数秒。

起始位置 $0$ 和位于 $b$ 的基地都有遮挡物，因此探测车在那里不会受到辐射伤害。

在返回基地的途中，探测车受到的最小伤害是多少？

例子

考虑如下情况，其中基地位于位置 $18$，位置 $8$ 和 $15$ 有藏身点。

假设脉冲星的周期为 $4$，那么不在藏身点的探测器会在 $4$，$8$，$12$ 等时刻受到伤害。如果探测器在 $0$ 时从起始位置（有遮挡的地方）出发，它可以在时刻 $8$ 到达第一个藏身点，在时刻 $4$ 会受到辐射伤害 $d$（但在 $8$ 时不会受到伤害，因为那时在藏身点）。如果探测器继续不停地前进，在时刻 $18$ 到达大本营，又会受到 $d + d$ 个单位的辐射伤害（分别在时刻 $12$ 和 $16$）。这样，它会受到 $d + d + d = 3d$ 个单位的辐射伤害和 $18$ 个单位的环境伤害。然而，如果探测器在第 $2$ 个藏身点（位置 $15$）等待 $1$ 单位时间，时刻 $16$ 的脉冲就不会对它造成任何伤害，它在时刻 $19$ 到达基地时总共只受到 $2d+19$ 单位的伤害。对于大多数 $d$ 值来说，这种情况都比较好。

如果脉冲星的周期为 $10$，那么探测车就可以在起始位置等待 $2$ 单位时间，然后直接回基地，无需在任何藏身点停留。这样，它就能在脉冲星耀斑出现的时刻恰好到达第一个藏身点（位置 $8$），并在时刻 $20$ 到达基地，总共受到 $20$ 单位环境伤害，而没有受到任何辐射伤害。

输入格式

第一行四个整数 $b,p,d,n$，分别表示基地的位置，脉冲星耀斑的频率，脉冲星耀斑带来的附加辐射伤害和藏身点个数。

接下来 $n$ 行，每行一个整数 $a_i$，表示藏身点的位置。保证 $0<a_1<\ldots<a_n<b$。

输出格式

输出一行一个整数，表示探测车要到达 $b$ 所受的最小伤害。

样例

样例 1

输入：

18 4 5 2
8
15

输出：

29

样例 2

输入：

18 4 0 2
8
15

输出：

18

样例 3

输入：

18 10 100 2
8
15

输出：

20

样例 4

输入：

18 4 100 0

输出：

418

样例 5

输入：

65 20 100 3
14
25
33

输出：

172

数据范围与提示

对于所有数据，满足：

• $1\le b\le 10^{12}$
• $0\le d\le 10^6$
• $0\le n\le 10^5$
• $p<b,n<b$

详细子任务附加限制及分值如下表：

子任务	附加限制	分值
1	$p\le 10^6$ 并且探测车在离开位置 $0$ 之后，探测车不需要等待	8
2	$b\le 1000,p\le 100,n\le 10$	5
3	$b\le 1000$	7
4	$p\le 10^6,n\le 1000$	15
5	$p\le 100$	20
6	$p\le 10^6$	35
7	无附加限制	10

• 在第一组子任务中，探测车在位置 $0$ 处开始移动之前可能还需要等待。例如，样例 $2,3,4$ 属于子任务 $1$。