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

Therefore, she chooses $m$ intervals $[l_i, r_i]$ and two positive integers $a$ and $k$. She intends to select exactly $k$ intervals from these $m$ intervals and perform an interval addition operation of $a$ on each selected interval. (Each interval can be selected at most once.)

Performing an addition of $a$ on an interval $[l, r]$ is defined as changing $A_i$ to $A_i + a$ for all $i \in [l, r]$.

Now, Kele wants to know how to choose the intervals such that the minimum value of the sequence after the operations is as large as possible, i.e., to maximize $\min \{ A_i \}$.

Input

The first line contains an integer representing 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 distinct.

Output

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

Examples

Input 1

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

Output 1

3

Note 1

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

Subtasks