There is a brain teaser that goes like this: there are two bridges, one high and one low, located very close to each other. After two floods, the high bridge was submerged twice, but the low bridge was only submerged once. Why? The answer is: because the low bridge is too low; after the first flood receded, the water level was still above the low bridge, so it does not count as being "submerged twice." For example:

Suppose the heights of the high bridge and the low bridge are 5 and 2, respectively, and the initial water level is 1. First flood: The water level rises to 6 (both bridges are submerged), then recedes to 2 (the high bridge is no longer submerged, but the low bridge remains submerged). Second flood: The water level rises to 8 (the high bridge is submerged again), then recedes to 3.

Indeed, it is a play on words. The key lies in the meaning of "again." If a bridge remains submerged after a flood recedes (i.e., the water level is not less than the height of the bridge), then it cannot be counted as being submerged "again" when the water level rises for the next flood.

Given the heights of $n$ bridges and the peak water level $a_i$ and receding water level $b_i$ for the $i$-th flood, count how many bridges have been submerged at least $k$ times. The initial water level is 1, and the peak water level of each flood is always greater than the receding water level of the previous flood.

Input

The input file contains at most 25 test cases. The first line of each test case contains three integers $n, m, k$ ($1 \le n, m, k \le 10^5$). The second line contains $n$ integers $h_i$ ($2 \le h_i \le 10^8$), representing the height of each bridge. The following $m$ lines each contain two integers $a_i$ and $b_i$ ($1 \le b_i < a_i \le 10^8$, $a_i > b_{i-1}$). The input file size does not exceed 5MB.

Output

For each test case, output the number of bridges that have been submerged at least $k$ times.

Examples

Input 1

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

Output 1

Case 1: 1
Case 2: 3