有个脑筋急转弯是这样的：有距离很近的一高一低两座桥，两次洪水之后高桥被淹了两次，低桥却只被淹了一次，为什么？答案是：因为低桥太低了，第一次洪水退去之后水位依然在低桥之上，所以不算“淹了两次”。举例说明：

假定高桥和低桥的高度分别是5和2，初始水位为1

第一次洪水：水位提高到6（两个桥都被淹），退到2（高桥不再被淹，但低桥仍然被淹）

第二次洪水：水位提高到8（高桥又被淹了），退到3。

没错，文字游戏。关键在于“又”的含义。如果某次洪水退去之后一座桥仍然被淹（即水位不小于桥的高度），那么下次洪水来临水位提高时不能算“又”淹一次。

输入n座桥的高度以及第i次洪水的涨水水位ai和退水水位bi，统计有多少座桥至少被淹了k次。初始水位为1，且每次洪水的涨水水位一定大于上次洪水的退水水位。

输入文件最多包含25组测试数据。每组数据第一行为三个整数n, m, k（1<=n,m,k<=105）。第二行为n个整数hi（2<=hi<=108），即各个桥的高度。以下m行每行包含两个整数ai和bi（1<=bi<ai<=108, ai>bi-1）。输入文件不超过5MB。

对于每组数据，输出至少被淹k次的桥的个数。

2 2 2
2 5
6 2
8 3
5 3 2
2 3 4 5 6
5 3
4 2
5 2

Case 1: 1
Case 2: 3

话说这其实是一年前在省赛上面遇到的题目，当时刚看完题目，就想着对每次洪水进行分析，在每次洪水来的时候，记录哪些桥被淹了，哪些桥没被淹，写出一大堆代码，得出结果之后交上去超时了，于是无缘三等奖 _(:зゝ∠)_

过了一年，重新来做这道题，发现其实应该换个角度切入，针对每座桥来做分析：
针对每座桥做分析的意思就是，只关注发生在该桥身上的事情。
题目倒数第二段里面有一句话非常重要：如果某次洪水退去之后一座桥仍然被淹（即水位不小于桥的高度），那么下次洪水来临水位提高时不能算“又”淹一次。
就是说不管来了多少次洪水，发生在某座桥上面的所有洪水次数是有可能少于总的洪水次数的（退水时没露出来，就当作是该桥还在经历同一次洪水）。

定好切入角度，接下来就是得出结果了。这里还有一点就是其实每次洪水的涨水水位跟退水水位不需要“绑定”在一起，可以单独处理。
下面来讲一个小故事说明这一点，顺便把得出结果的原因写出来：
假设我们来到一座桥。
它的管理员告诉我们一些它的“历史水位记录”：在经历过的这么多次的洪水之中，退水水位比桥要低的有 a 次。那么我们就可以猜想，这座桥应该被淹过 a 次。
后来经过我们调查得知：其实在经历过的这么多次洪水里面，其实有 b 次的涨水水位都没超过桥。
因为涨水水位一定会比退水水位高，所以那 b 次洪水里面的退水水位都一定比桥低，在前面我们根据退水水位推测桥被淹次数的时候已经把这 b 个退水水位算进去了，而显然这 b 次洪水是不能算到桥被淹次数里面去的，所以桥被淹次数应该是 (a - b) 次。

从上面的小故事我们可以看出，其实最终结果就是 (a - b)。

我们不用关心退水水位对应的涨水水位是哪一个（也就是说知道某一次洪水的退水水位低于桥，我们也不必担心其对应的涨水水位是否高于桥），因为我们只需要统计比桥低的次数。所以可以先对涨水水位和退水水位分别进行排序，然后找出最后一个符合要求的水位排在第几位，就知道次数了。