Description

Kelian has a positive integer sequence $A$ of length $n$, but she feels the numbers in $A$ are too small, which makes her unhappy.

So she chooses $m$ intervals $[l_i,r_i]$ and two positive integers $a,k$. She plans to select exactly $k$ intervals from these $m$ intervals, and perform one range add $a$ operation on each selected interval. (Each interval can be selected at most once).

Performing a +$a$ operation on a range $[l,r]$ is defined as: for all $i$ ∈ $[l,r]$, set $A_i$ to $A_i+a$. Now Kelian wants to know how to choose the intervals so that the minimum value of the sequence after the operations is as large as possible, i.e., maximize $\min\{A_i\}$.

Input Format

The first line contains an integer indicating the number of test cases.

For each test case, the first line contains four integers $n,m,k,a$.

The second line contains $n$ integers describing the sequence $A$.

The next $m$ lines each contain two integers $l_i,r_i$ describing each interval. It is guaranteed that all intervals are pairwise distinct.

Output Format

For each test case, output one integer representing the maximum possible minimum value of the sequence after the operations.

1 
3 3 2 1
1 3 2
1 1
1 3
3 3

3

Hint

Choose to add $1$ to intervals $[1,1]$ and $[1,3]$.

For $100\%$ of the testdata, it is guaranteed that $1\leq\sum n,\sum m\leq 2\times 10^5$, $1\leq T\leq 2\times 10^5$, $1\le k\le m$, $1\le a\le 100$, $1\le A_i\le 10^8$.

Translated by ChatGPT 5