Minimizing Time and Cost on a Number Line

You are on a number line, starting at coordinate 0 at the end of second $0$. Your goal is to reach coordinate $b$. Each second, you may either move one step forward (i.e. increase your coordinate by $1$) or wait (i.e. keep your coordinate unchanged).

You are given a positive integer $p$ and a nonnegative integer $d$, as well as a set of additional safe coordinates $\{a_1, a_2, \dots, a_n\}$. For every nonnegative integer $k\ge 0$, if at the end of second $kp$ your coordinate is not one of the safe positions (which are defined as $0$, $b$, or any of $a_1, a_2, \dots, a_n$), then a penalty of $d$ is incurred.

Find the minimum possible sum of the total time taken (in seconds) and the total incurred cost (penalties) required to reach coordinate $b$.

inputFormat

The first line contains four integers: $b$, $p$, $d$, and $n$, where:

• $b$ ($b\ge 1$) is the target coordinate.
• $p$ ($p\ge 1$) is the period at which a cost check is performed.
• $d$ ($d\ge 0$) is the penalty incurred if the coordinate at a cost check is unsafe.
• $n$ is the number of additional safe coordinates.

The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$, representing the additional safe coordinates. Note that coordinates $0$ and $b$ are always considered safe.

outputFormat

Output a single integer: the minimum sum of the total time (in seconds) and the incurred penalty.

sample

5 2 10 1
3

16