Trên trục ~Ox~, cho ~M~ điểm có toạ độ nguyên dương được đánh số từ ~1~ đến ~M~: ~a_1, a_2, \dots, a_M~ và ~N~ đoạn thẳng ~[l_i, r_i]~ đượ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 ~[l_i, r_i]~ 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 ~[l_i, r_i]~;
• 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 thoả 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 từ tệp văn bản SEGMENT.INP:

• Dòng đầu tiên gồm ba số nguyên ~M, N, K~ ~(0 \le K \le N \le M \le 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 ~a_1, a_2, \dots, a_M~ ~(1 \le i \le M; \ a_i \le 10^9)~;
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~l_i, r_i~ ~(1 \le i \le N; \ l_i \le r_i \le 10^9)~ mô tả đoạn thẳng thứ ~i~.

Kết quả ghi ra tệp văn bản SEGMENT.OUT:

Gồm 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.

Ví dụ

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]~).

~\Rightarrow~ ~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 thoả mãn, kết thúc.

~\Rightarrow~ ~3~ lần sử dụng lựa chọn ~1~.

Ràng buộc

• Có ~10\%~ số test ứng với ~10\%~ số điểm có ~M \le 10~;
• ~10\%~ số test khác ứng với ~10\%~ số điểm có ~M \le 20~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~M \le 10^3~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~M \le 10^5;~ ~K=0~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~M \le 10^5~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.