31346번 - Candies 다국어

문제

$n$ bobo are playing a game about candies. bobo are labeled by 1,ドル 2, \dots, n$ for convenience. Initially, the $i$-th bobo has $a_i$ candies in hand.

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

The 1ドル$-st bobo is their leader. So he can get at most $y$ more candies from some unknown source before the start of the game. Now he wonder the maximum number of candies he can have after the $m$ rounds.

입력

The first line contains 4ドル$ 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$).

출력

A single integer denotes the maximum number of candies.

제한

힌트