题目描述

可怜有一个长度为 $n$ 的正整数序列 $A$ ,但是她觉得 $A$ 中的数字太小了,这让她很不开心。
于是她选择了 $m$ 个区间 $[l_i , r_i]$ 和两个正整数 $a$ , $k$ 。她打算从这 $m$ 个区间里选出恰好 $k$ 个区间,并对每个区间执行一次区间加 $a$ 的操作。 (每个区间最多只能选择一次。)

对区间 $[l, r]$ 进行一次加 $a$ 操作可以定义为对于所有 $i \in [l, r]$ ,将 $A_i$ 变成 $A_i + a$ 。
现在可怜想要知道怎么选择区间才能让操作后的序列的最小值尽可能的大,即最大化 $ \min \{ A_i \} $ 。

输入格式

第一行输入一个整数表示数据组数。
对于每组数据第一行输入四个整数 $n,m,k,a$ 。
第二行输入 $n$ 个整数描述序列 $A$ 。
接下来 $m$ 行每行两个整数 $l_i,r_i$ 描述每一个区间。数据保证所有区间两两不同。

输出格式

对于每组数据输出一个整数表示操作后序列最小值的最大值。

样例

input

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

output

3

选择给区间 $[1, 1]$ 和 $[1, 3]$ 加 $1$ 。

数据范围与提示