P4064 [JXOI2017] Addition

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\}$.

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.

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

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