Коровы Фермера Джона учатся переходить через дорогу эффективно.
И ищут цыплят в качестве учителей.
Цыплята очень занятые существа и имеют ограниченное время для помощи коровам.
Всего имеется \(C\) цыплят на ферме (\(1 \leq C \leq 20,000\)), последовательно
пронумерованных \(1 \ldots C\), и каждый цыплёнок \(i\) может помогать коровам
ровно время \(T_i\). Коровы никуда не торопятся. Всего имеется \(N\) коров на ферме
(\(1 \leq N \leq 20,000\)), последовательно пронумерованных \(1 \ldots N\), и корова
\(j\) способно переходить дорогу между временами \(A_j\) и \(B_j\). В идеале корова
\(j\) хочет найти цыплёнка \(i\), который поможет её перейти через дорогу. Для того,
чтобы их расписания были совместимы, необходимо чтобы выполнялось неравенство
\(A_j \leq T_i \leq B_j\).
Если для каждой коровы может быть взят в пару не более чем один цыплёнок
и каждый цыплёнок может быть взят в пару не более чем с одной коровой, помогите
найти максимальное количество пар корова-цыплёнок, которого можно достичь.
ФОРМАТ ВВОДА (файл helpcross.in):
Первая строка ввода содержит \(C\) и \(N\). Следующие \(C\) строк содержат \(T_1 \ldots T_C\),
а последующие \(N\) строк содержат \(A_j\) и \(B_j\) (\(A_j \leq B_j\)) для \(j = 1 \ldots N\).
\(A\), \(B\), \(T\)' – все неотрицательные числа (не обязательно различные) не более
1,000,000,000.
ФОРМАТ ВВОДА (файл helpcross.out):
Вычислите максимально-возможное количество пар корова-цыплёнок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
7
8
6
2
9
2 5
4 9
0 3
8 13
|
3
|