#2274. 「JXOI2017」加法

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: resCreator

题目描述

可怜有一个长度为 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 描述每一个区间。数据保证所有区间两两不同。

输出格式

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

样例

样例输入

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

样例输出

3

样例解释

选择给区间 [1, 1] [1, 3] 1

数据范围与提示

测试点编号 \sum n \sum m
1 \leq 20
2

  3

\leq 2000
4
5
6
7 \leq 2 \times 10^5
8
9
10