题目描述

你在一条数轴上，初始（第 $0$ 秒末）你的坐标是 $0$，你要移动到坐标为 $b$ 的点上。每一秒，你都可以选择向前移动一步（坐标 $+1$）或等待（坐标不变）。给定正整数 $p$ 和非负整数 $d$，对于每个非负整数 $k\ge 0$，若第 $kp$ 秒末，你的坐标不为 $0$，$b$，也不为给定的 $a_1,a_2,\cdots,a_n$ 中的一个，则会产生 $d$ 的代价。你要最小化到达坐标为 $b$ 的点的时间和产生的代价之和。输出这个最小值。请注意数据满足 $0<a_1< \dots <a_n < b$。

输入格式

第一行四个非负整数 $b,p,d,n$。

接下来 $n$ 行，第 $i$ 行一个正整数 $a_i$。

输出格式

一行一个非负整数表示答案。

18 4 5 2
8
15

29

18 4 0 2
8
15

18

18 10 100 2
8
15

20

18 4 100 0

418

65 20 100 3
14
25
33

172

提示

【样例解释】

样例 #1 中，一种最优方案是先一直走到坐标为 $15$ 的点，等待 $1$ 秒，再花 $3$ 秒走到终点。总耗时 $19$ 秒，在第 $4$ 秒末和第 $12$ 秒末各产生了 $d=5$ 的代价。答案为 $19+2\times5=29$。

样例 #2 中，一种最优方案是直接走到终点，总耗时 $18$ 秒。因为 $d=0$，不会产生代价，答案为 $18$。

样例 #3 中，一种最优方案是在原点等待 $2$ 秒再直接走到终点，总耗时 $20$ 秒，没有产生代价，答案为 $20$。

【数据范围】

对于 $100\%$ 的数据，$1\le p<b\le 10^{12}$，$0\le d\le 10^6$，$0\le n\le 10^5$，$n<b$。

$[1]$：离开坐标为 $0$ 的点之前仍然可能需要等待。例如，样例 #2、样例 #3 和样例 #4 均符合子任务 $1$ 的要求。