#P5321. [Jxoi2017]加法

    ID: 4334 传统题 1000ms 512MiB 尝试: 169 已通过: 85 难度: 6 上传者: 标签>难度分类提高排序与序列处理二分答案贪心堆贪心差分标记区间修改交换论证CF2000

[Jxoi2017]加法

[JXOI2017] 加法

题目描述

可怜有一个长度为 nn 的正整数序列 AA,但是她觉得 AA 中的数字太小了,这让她很不开心。

于是她选择了 mm 个区间 [li,ri][l_i,r_i] 和两个正整数 a,ka,k。她打算从这 mm 个区间里选出恰好 kk 个区间,并对每个区间执行一次区间加 aa 的操作。(每个区间最多只能选择一次)。

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

输入格式

从标准输入读入。第一行一个整数 TT,表示数据组数。

对于每组数据第一行输入四个整数 n,m,k,an,m,k,a。

第二行输入 nn 个整数描述序列 AA。

接下来 mm 行每行两个整数 li,ril_i,r_i 描述每一个区间。所有区间均满足 1≤li≤ri≤n1\le l_i\le r_i\le n,且两两不同。

输出格式

向标准输出对每组数据写出一行一个整数表示操作后序列最小值的最大值。

样例 #1

样例输入 #1

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

样例输出 #1

3

提示

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

对于 100%100\% 的数据,保证 1≤∑n,∑m≤2×1051\leq\sum n,\sum m\leq 2\times 10^5,1≤T≤2×1051\leq T\leq 2\times 10^5,1≤k≤m1\le k\le m,1≤a≤1001\le a\le 100,1≤Ai≤1081\le A_i\le 10^8。