Description

T has a bucket made of $n$ vertical wooden planks. The height of the $i$-th plank is $a_i$. To increase the bucket's water-holding capacity, she plans to install some additional planks.

T has two types of planks available: $m$ planks of height $1$, and $k$ planks of height $h$. Each of these planks can be installed on top of one of the bucket's original planks. Multiple planks can be stacked on a single original plank. After installation, an original plank and all planks added on top of it are considered a single plank, and its new height is the sum of their individual heights.

Since the water-holding capacity is determined by the shortest plank, T wants to know what is the maximum possible height of the shortest plank after adding the new planks.

Input Format

The first line contains four integers: $n, m, k, h$.

The second line contains $n$ positive integers $a_1, \dots, a_n$, representing the initial heights of the planks.

Output Format

Output a single line containing a positive integer, which is the answer.

3 5 1 3
2 5 4

6

4 10 2 5
10 11 12 13

16

5 10 0 100
1 2 3 4 5

5

Hint

【Sample 1 Explanation】

We can add 4 planks of height 1 to the first original plank, 1 plank of height 1 to the second original plank, and 1 plank of height 3 to the third original plank. The heights of the three planks then become $6, 6, 7$. The height of the shortest plank is $6$.

【Data Constraints】

• Special Property: $a_1=a_2=\dots=a_n$.

For all test cases, it is guaranteed that: $1\le n\le 10^5$, $0\le m,k\le 10^9$, $1\le a_i\le 10^9$, $2\le h\le 10^9$.