问题标题: 酷丁编程：Hello,World!

题目链接： 酷丁编程：5279

题目描述 De**ion

可怜有一个长度为 nn 的正整数序列 AA ,但是她觉得 AA 中的数字太小了,这让她很不开心。于是她选择了 mm 个区间 [li,ri][li​,ri​] 和两个正整数 aa , kk 。她打算从这 mm 个区间里选出 恰好 kk个区间,并对每个区间执行一次区间加 aa 的操作。 (每个区间最多只能选择一次。)

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

输入描述 Input De**ion

第一行输入一个整数表示数据组数。
对于每组数据第一行输入四个整数 n,m,k,an,m,k,a 。
第二行输入 nn 个整数描述序列 AA 。
接下来 mm 行每行两个整数 li,rili​,ri​ 描述每一个区间。数据保证所有区间两两不同。

输出描述 Output De**ion

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

样例输入 Sample Input

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

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

样例解释

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