题目描述

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

举例说明：假定高桥和低桥的高度分别是 $5$ 和 $2$，初始水位为 $1$。第一次洪水：水位提高到 $6$（两个桥都被淹），退到 $2$（高桥不再被淹，但低桥仍然被淹）。第二次洪水：水位提高到 $8$ （高桥又被淹了），退到 $3$。

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

现在一个类似的问题交给你了：输入 $n$ 座桥的高度以及第 $i$ 次洪水的涨水水位 $a_i$ 和退水水位 $b_i$，统计有多少座桥至少被淹了 $k$ 次。初始水位为 $1$，输入数据保证每次洪水的涨水水位一定大于上次洪水的退水水位。

输入格式

每个测试点包含多组测试数据。

每组数据第一行为三个整数 $n,m,k$；

第二行为 $n$ 个整数 $h_i$，即各个桥的高度；

以下 $m$ 行每行包含两个整数 $a_i$ 和 $b_i$。

输出格式

对于每组数据，输出至少被淹 $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

数据范围与提示

对于 $10\%$ 的数据，每个测试点至多有 $1$ 组数据，$0\lt n\le 100, 0\lt k\le 50 , 0\lt h_i,a_i,b_i\le 10^4$；

对于 $20\%$ 的数据，每个测试点至多有 $5$ 组数据，$0\lt n\le 1000 , 0\lt k\le 500 , 0\lt h_i,a_i,b_i\le 10^5$；

对于 $40\%$ 的数据，每个测试点至多有 $5$ 组数据，$0\lt n\le 10^4 , 0\lt k\le 5000 , 0\lt h_i,a_i,b_i\le 10^6$；

对于 $80\%$ 的数据，每个测试点至多有 $10$ 组数据，$0\lt n\le 10^5 , 0\lt k\le 5\times 10^4 , 0\lt h_i,a_i,b_i\le 10^8$；

对于 $100\%$ 的数据，每个测试点至多有 $25$ 组数据，$0\lt n\le 10^5 , 0\lt k\le 5\times 10^4, 0\lt h_i,a_i,b_i\le 10^8$；

除此以外没有提示。

**来源：**湖南省第九届大学生计算机程序设计竞赛