Candy Dream

Little A had a candy‐colored dream and decided to buy some candies for his n friends. Initially, each child has 0 candies, and the i-th child requires at least a_i candies.

Little A can obtain candies by three types of operations:

1. Retail Purchase: Choose a single child and buy one candy for that child at a cost of 1.
2. Bulk Purchase: Choose a contiguous segment of children of length l (with l ≥ k) and buy one candy for each child in the segment. This operation costs l-B (in yuan).
3. Bulk Recycling: Choose a contiguous segment of children of length l (with l ≥ k) and take back (remove) one candy from each child in the segment, obtaining C yuan (i.e. the cost decreases by C).

All operations may be applied arbitrarily many times and in any order. In the end, the number of candies each child receives (which is the net result of additions and removals) must be at least a_i for every i (1 ≤ i ≤ n). Note that the operations are additive so that a bulk operation will add (or subtract) 1 candy uniformly to all children in that segment.

Your task is to determine the minimum total cost to satisfy all children’s requirements.

Note: It is guaranteed that the parameters are such that no arbitrage is possible (i.e. you cannot decrease the cost arbitrarily by using the recycling operations repeatedly).

inputFormat

The first line contains four integers: n, k, B and C (1 ≤ n ≤ 10, 1 ≤ k ≤ n, and B, C are integers).

The second line contains n integers: a₁, a₂, …, a_n (0 ≤ a_i ≤ 10), where a_i is the minimum number of candies required by the i-th child.

outputFormat

Output a single integer, which is the minimum total cost to ensure that every child ends up with at least the required number of candies.

sample

3 2 1 1
1 1 1

2