P14115 [IAMOI R4] The Bucket Effect

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.

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 a single line containing a positive integer, which is the answer.

**【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】** |Subtask #|$n\le$|$m\le$|$k\le$|$h\le$|Special Property| |:---:|:---:|:---:|:---:|:---:|:---:| |$1$|$10$|$3$|$3$|$10^9$|None| |$2$|^|^|$10^3$|^|^| |$3$|^|$10^3$|$3$|^|^| |$4$|$10^5$|$0$|$10^5$|^|^| |$5$|^|$10^5$|$0$|^|^| |$6\sim 8$|^|^|$10^5$|^|^| |$9,10$|^|$0$|$10^9$|^|^| |$11,12$|^|$10^9$|$0$|^|^| |$13,14$|^|^|$10^9$|$2$|^| |$15,16$|^|^|^|$10^9$|Yes| |$17\sim 20$|^|^|^|^|None| - 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$.