I - Implementation Addict

Contest Duration: 2015-12-20(Sun) 04:00 - 2015-12-20(Sun) 07:00 (local time) (180 minutes)

I - Implementation Addict Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

Problem

Wolf Sothe loves implementing online judge problems, he wants to solve as many problems as possible. However, if he keeps solving problems every day without a rest, day by day the number of problems that can be solved in a day will reduce.

So, sometimes Wolf Sothe takes a day off. On that day, Wolf Sothe will not solve any problem, then for the next day and later Wolf Sothe will be able to solve problems.

The number of problems that Wolf Sothe can solve in a day is as follows:

If that day is a working day, we define the number of days that Wolf Sothe has kept solving problems as $k$ (not including that day). Then Wolf Sothe can solve $max(0, A − k \times B)$ problems during that day.
If that day is a rest day, during that day no problem will be solved.

Wolf Sothe wants to solve problems for $N$ days. Let the $N$ days be as a sequence from the 1st day to the $N_{th}$ day. Suppose that Wolf Sothe doesn't solve problems before the 1st day.

In addition, we known in advance that there are some decided rest days.

A list of all the decided rest days will be given. For any other day, you can mark it as a rest day or a working day. Please find the maximum value of the number of problems that can be solved during $N$ days.

Input

Inputs will be given by standard input in following format

 $N$   $A$   $B$   $M$ 
 $t_1$ 
 $t_2$ 
:
 $t_M$

For the first line, integer $N(1≦N≦1,000,000,000)$ , $A(1≦A≦1,000,000,000)$ , $B(1≦B≦1,000,000,000)$ , $M(0≦M≦100,000)$ will be given divided by spaces. $M$ represents the number of the decided rest days.
From the second line there are $M$ additional lines to give the information about decided rest days. For the $i_{th}$ line, an integer $t_i(1≦t_i≦N)$ that represents the $t_i$ th decided rest day will be given. Please note that if $i < j$ , then $t_i<t_j$

Output

Please output the maximum value of the number of problems that can be solved during $N$ days in one line.

Print a newline at the end of output.

Input Example 1Copy

Copy

5 6 2 0

Output Example 1Copy

Copy

Suppose that Wolf Sothe rest on the 3rd day and solve problems on the remaining $4$ days.

For the 1st day, Wolf Sothe has kept solving problems for $0$ day. Thus, $max(0, 6 − 0 \times 2) = 6$ problems.
For the 2nd day, Wolf Sothe has kept solving problems for $1$ day. Thus, $max(0,6 − 1 \times 2) = 4$ problems.
For the 3rd day, Wolf Sothe rests. Thus, $0$ problem.
For the 4th day, Wolf Sothe has kept solving problems for $0$ day. Thus, $max(0, 6 − 0 \times 2) = 6$ problems.
For the 5th day, Wolf Sothe has kept solving problems for $1$ day. Thus, $max(0, 6 − 1 \times 2) = 4$ problems.

In conclusion, $6 + 4 + 0 + 6 + 4 = 20$ will be solved in total.

Input Example 2Copy

Copy

6 4 3 1
3

Output Example 2Copy

Copy

Input Example 3Copy

Copy

Output Example 3Copy

Copy