Đàn bò của Farmer John đang cố học cách băng qua đường hiệu quả. Nhớ đến câu đùa cũ "tại sao con gà băng qua đường?", chúng cho rằng gà hẳn là chuyên gia băng qua đường nên lên đường tìm gà giúp đỡ.

Hóa ra gà là những sinh vật rất bận rộn và chỉ có ít thời gian để giúp đàn bò. Có \(C\) con gà trong trang trại (\(1 \leq C \leq 20,000\)), được đánh số thuận tiện từ \(1 \ldots C\), và mỗi con gà \(i\) chỉ sẵn lòng giúp một con bò vào đúng thời điểm \(T_i\). Đàn bò không bao giờ vội nên có lịch trình linh hoạt hơn. Có \(N\) con bò trong trang trại (\(1 \leq N \leq 20,000\)), được đánh số thuận tiện từ \(1 \ldots N\), trong đó bò \(j\) có thể băng qua đường trong khoảng thời gian từ \(A_j\) đến \(B_j\). Cho rằng đi theo cặp là cách tốt nhất, mỗi bò \(j\) muốn tìm một gà \(i\) giúp mình băng qua đường; để lịch trình của chúng tương thích, \(i\) và \(j\) phải thỏa mãn \(A_j \leq T_i \leq B_j\).

Nếu mỗi con bò chỉ có thể được ghép với nhiều nhất một con gà và mỗi con gà chỉ có thể được ghép với nhiều nhất một con bò, hãy tính số cặp bò-gà lớn nhất có thể tạo thành.

Dữ liệu vào

Dòng đầu tiên chứa \(C\) và \(N\). \(C\) dòng tiếp theo chứa lần lượt \(T_1 \ldots T_C\), và \(N\) dòng tiếp theo chứa \(A_j\) và \(B_j\) (\(A_j \leq B_j\)) với \(j = 1 \ldots N\). Các giá trị \(A\), \(B\) và \(T\) đều là số nguyên không âm (không nhất thiết phân biệt) không quá 1.000.000.000.

Dữ liệu ra

In ra số cặp bò-gà lớn nhất có thể tạo thành.

Ví dụ

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

3

Nguồn

USACO 2017 February Contest, Silver — Why Did the Cow Cross the Road. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=714