Trên trục Ox, cho M điểm có toạ độ nguyên dương được đánh số từ 1 đến M: a1, a2,., aM và N đoạn thẳng [li, ri| được đánh số từ 1 đến N (không có đoạn thẳng nào nằm trong nhau).

Xét lần lượt các đoạn thắng, với đoạn thắng thứ i là đoạn [li, ri] có hai lựa chọn như sau:

• Lựa chọn 1: Chọn ra một điểm từ tập các điểm đã cho (điểm này chưa được chọn trước đó), sao cho điểm đó không nằm trong đoạn [li, ri];

• Lựa chọn 2: Bỏ qua đoạn thẳng này.

Yêu cầu: Chỉ được sử dụng lựa chọn 2 nhiều nhất K lần, tính số lượng lựa chọn 1 được sử dụng nhiều nhất. Chú ý, nếu sử dụng hết K lần lựa chọn 2 và không chọn được điểm thỏa mãn lựa chọn 1 thì kết thúc việc xét các đoạn thẳng.

Dữ liệu vào:

• Dòng đầu tiên gồm ba số nguyên M, N, K (0 ≤ K ≤ N ≤ M ≤ 10^6) là số lượng điểm, số lượng đoạn thẳng và số lần tối đa sử dụng lựa chọn 2;

• Dòng thứ hai chưa M số nguyên dương a1, a2,..., aM (1 ≤ i ≤ M; ai ≤ 10^9);

• N dòng tiếp theo, dòng thứ i chứa hai số nguyên dương li; ri (1 ≤ i ≤ N; li ≤ ri ≤ 10^9) mô tả đoạn thẳng thứ i.

Kết quả in ra một số nguyên duy nhất là số lần lựa chọn 1 được sử dụng nhiều nhất.

Input:

5 3 2
1 3 4 2
1 4
2 5
3 6

Output:

2

Giải thích:

Đoạn thắng 1: Sử dụng lựa chọn 2;

Đoạn thẳng 2: Sử dụng lựa chọn 1, chọn điểm thứ 1 có toạ độ là 1 (không nằm trong đoạn [2,5]);

Đoạn thẳng 3: Sử dụng lựa chọn 1, chọn điểm thứ 4 có toạ độ là 2 (không nằm trong đoạn [3, 6]).

→ 2 lần sử dụng lựa chọn 1.

Input:

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

Output:

3

Giải thích:

Đoạn thẳng 1: Sử dụng lựa chọn 1, chọn điểm thứ 2 có toạ độ là 7;

Đoạn thẳng 2: Sử dụng lựa chọn 1, chọn điểm thứ 1 có toạ độ là 4;

Đoạn thẳng 3: Sử dụng lựa chọn 1, chọn điểm thứ 4 có toạ độ là 7;

Đoạn thẳng 4: Không chọn được điểm thỏả mãn, kết thúc.