Candies

Interview

Time limit1sMemory limit1024 MB

Summary

Given n counts and a bonus of up to y for bobo 1, find the most candies bobo 1 can hold after m rounds, where each round the minimum (ties to the smallest label) gets x.

Level: Medium5 of 10
Topics: Heap, Simulation, Greedy
Solved: No attempts yet

Problem

$n$ bobo are playing a game about candies. The bobo are labeled $1, 2, \dots, n$ for convenience. Initially, the $i$ -th bobo holds $a_i$ candies.

The game is played in $m$ rounds. In each round, the bobo with the fewest candies is awarded $x$ candies. If two or more bobo have the same number of candies, the bobo with the smallest label gets the prize.

The 1st bobo is their leader. Before the game starts, he can receive up to $y$ more candies from some unknown source. Find the maximum number of candies he can have after the $m$ rounds.

Input

The first line contains four integers $n$ , $m$ , $x$ , $y$ ( $1 \leq n, m \leq 200000$ , $1 \leq x, y \leq 10^9$ ).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \leq a_i \leq 10^9$ ).

Output

Print a single integer: the maximum number of candies the 1st bobo can have after the $m$ rounds.

Examples1

Example 1
Input
```
2 1 2 2
1 2
```
Expected output
```
4
```