3894. [桐柏一中邀请赛S13]树

【题目描述】

Yoimiya 种下的樱树已经长出了$n$ 棵，它们从左到右排成了一行，编号分别为 $1,2,\cdots,n$。这些树一开始的高度为$h_1,h_2,\cdots,h_n$。现在 Yoimiya 要给这些树浇水。

然而 Yoimiya 并不想自己动手，因此她找来了 $m$ 个帮手，其中第 $i$ 个帮手会帮助她给编号在 $[l_i ,r_i ]$内的所有树浇水，使得这个区间内的所有树的高度都增长一个单位；即对所有 $l_i ≤ j ≤ r_i$ ，使 $h_j \leftarrow h_j +1$。

由于 Yoimiya 善解人意，因此她打算只选择这 $m$ 个帮手中的 $k$ 个来帮忙。她希望在这 $k$ 个帮手完成浇水之后，所有树中最高的那个尽可能高。请你帮她求出，在这 $k$ 个帮手完成浇水之后，所有树中最高的那个最高能有多高。

【输入格式】

第一行三个正整数 $n,m,k$。

第二行 $n$ 个正整数 $h_1,h_2,\cdots,h_n$ ，表示每棵树初始的高度。

接下来 $m$ 行，第 $i + 2$ 行有两个正整数 $l_i ,r_i$ ，表示第 $i$ 个帮手选择的区间。

【输出格式】

输出一行一个正整数，表示在这 $k$ 个帮手完成浇水之后，所有树中最高的那个最高能有多高。

【样例1输入】

5 4 2
1 3 2 5 5
1 4
2 4
1 2
1 3

【样例1输出】

7

【样例1说明】

应当选择浇水区间为 $[1,4],[2,4]$ 的两个帮手，最终树的高度为 $h = (2,5,4,7,5)$，最大值为 $7$。

【样例2下载】

样例下载

【数据规模与约定】

对于所有测试点：$1 ≤ n,m,k ≤ 2 \times 10^5 ，1 ≤ h_i ≤ 2 \times 10^5 ，1 ≤ l_i ≤ r_i ≤ n$。

每个测试点的具体限制见下表：

特殊性质 A：$k = m$。

特殊性质 B：对于 $1 ≤ i ≤ m，l_i = r_i$。

【来源】

桐柏一中邀请赛S13 Task2