Maximize Minimum Value after Interval Additions

You are given a positive integer sequence \(A\) of length \(n\) and \(m\) intervals \( [l_i, r_i] \). In addition, you are given two positive integers, \(a\) and \(k\). You must choose exactly \(k\) distinct intervals (each interval can be chosen at most once) and perform the following operation on each chosen interval: for an interval \([l,r]\), add \(a\) to every element \(A_i\) for all \(i\) in \([l, r]\).

Your goal is to maximize \(\min\{A_i\}\) after the operations. Equivalently, if an index \(i\) is covered by \(c_i\) chosen intervals, the final value at index \(i\) becomes \(A_i + a \times c_i\). Determine the maximum possible value of \(\min_{1 \le i \le n} (A_i + a\,c_i)\).

Note: All indices are 1-indexed and if \(T\) is the final minimum value, then for each \(i\) we must have \(A_i + a\, c_i \ge T\). In other words, the number of chosen intervals covering index \(i\) must be at least \(\left\lceil \frac{T - A_i}{a} \right\rceil\) (if \(A_i < T\)).

inputFormat

The first line contains four space-separated integers: \(n\), \(m\), \(a\), and \(k\).

The second line contains \(n\) space-separated positive integers representing the sequence \(A\).

Each of the following \(m\) lines contains two space-separated integers \(l_i\) and \(r_i\), denoting an interval.

outputFormat

Output a single integer denoting the maximum possible minimum value of the sequence after performing the operations.

sample

5 3 2 2
1 2 3 4 5
1 3
2 5
3 5

3