题目描述

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

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

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

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

输入描述

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

第二行给出 $n$ 个正整数 $a_1,a_2,\dots,a_n$ 其中 $a_i$ 表示第 $i$ 个员工的忍耐度。

接下来的 $m$ 行，第 $i$ 行给出两个正数 $l_i,r_i$表示第 $i$ 次打回方案后会致使 $l_i \sim r_i$的组员怒气值 $+1$。

输出描述

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

输入样例1

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

输出样例1

3

样例解释

设序列 $b$ 表示组员的怒气，其中 $b_i$ 表示第 $i$ 个组员的怒气值。

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

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

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

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

数据范围

对于所有测试点：$1 \leq n, m \leq 3 \times 10^5, 1\leq k \leq n$,$1 \leq a_i \leq 3 \times 10^5$, $1 \leq l_i \leq r_i \leq n$。