#H1038. HtGPT

HtGPT

题目描述

卉图信息科技有限公司最近接到了一个制作 HtGPT 的项目,由你担任项目组组长。小组里有 nn 个人,组员编号为 1n1 \sim n

该组成员共同给出了一套方案,但是你觉得不够完美,于是打回了 mm 次让小组重改。每次打回会致使编号为 liril_i \sim r_i 的组员怒气值 +1+1。每个组员都有一个忍耐度 aia_i,如果一个组员的怒气值达到了他的忍耐度,那么他便忍无可忍去找你申请退组,当然你肯定不会让他退组。而如果有 kk 人找你申请退组,为了项目稳定运行,你会决定直接使用当前版的方案。

最初的方案版本为第 00 版,第 ii 次被打回后所得到的是第 ii 版 。特别的,如果 mm 次改版后依旧没有至少 kk 个人找找你申请退组,那么直接采用最后一版方案。

请找出第几版方案最后被使用。

输入描述

第一行给出三个正整数 n,m,kn,m,k

第二行给出 nn 个正整数 a1,a2,,ana_1,a_2,\dots,a_n 其中 aia_i 表示第 ii 个员工的忍耐度。

接下来的 mm 行,第 ii 行给出两个正数 li,ril_i,r_i表示第 ii 次打回方案后会致使 liril_i \sim r_i的组员怒气值 +1+1

输出描述

输出一行一个整数,代表你最后采用了第几版方案。

输入样例1

7 5 3
1 3 2 4 8 6 2
1 4
2 7
2 2
4 7
5 6

输出样例1

3

样例解释

设序列 bb 表示组员的怒气,其中 bib_i 表示第 ii 个组员的怒气值。

11 次被打回后,141 \sim 4 号组员的怒气值 +1+1,此时 b=[1,1,1,1,0,0,0]b = [1,1,1,1,0,0,0]11 号组员的怒气值达到了他的忍耐度。

22 次被打回后,272 \sim 7 号组员的怒气值 +1+1,此时 b=[1,2,2,2,1,1,1]b = [1,2,2,2,1,1,1]33 号组员的怒气值达到了他的忍耐度。

33 次被打回后,222 \sim 2 号组员的怒气值 +1+1,此时 b=[1,3,2,2,1,1,1]b = [1,3,2,2,1,1,1]22 号组员的怒气值达到了他的忍耐度;

此时共有 33 名组员找你申请退组,为了项目稳定运行,你决定直接使用当前版的方案, 即第 33 版。

数据范围

测试点编号 nn\leq 特殊性质
161 \sim 6 500500
7127 \sim 12 10510^{5} li=1l_i = 1, 且 1j<m1 \leq j < m 时,有 rjrj+1 r_j \leq r_{j+1}
132013 \sim 20 3×1053 \times 10^{5}

对于所有测试点:1n,m3×105,1kn1 \leq n, m \leq 3 \times 10^5, 1\leq k \leq n,1ai3×1051 \leq a_i \leq 3 \times 10^5, 1lirin1 \leq l_i \leq r_i \leq n