Чому корова перейшла дорогу (Срібло)#10535

Чому корова перейшла дорогу (Срібло)

1 секунда

128 мегабайтів

Середня

Корови Фермера Джона намагаються навчитися безпечно та ефективно переходити дорогу. Згадавши старий жарт «Чому курка перейшла дорогу?», вони вирішили, що кури, мабуть, справжні експерти з переходу доріг, і вирушили шукати курей, які могли б їм допомогти.

Як виявилося, кури — дуже зайняті створіння, і в них є лише обмежений час для допомоги коровам. На фермі є $c$ курей, пронумерованих для зручності числами $1 \dots c$ , і курка $i$ готова допомогти корові лише в момент часу $t_{i}$ t_i. Корови, які нікуди не поспішають, мають гнучкіший графік. На фермі є $n$ корів, пронумерованих для зручності числами $1 \dots n$ , причому корова $j$ може перейти дорогу в будь-який момент часу від $A_{j}$ A_j до $B_{j}$ B_j включно.

Використовуючи систему «напарників», кожна корова $j$ хотіла б знайти курку $i$ , яка допоможе їй перейти дорогу. Їхні розклади сумісні, якщо виконується умова

$A_{j} \leq t_{i} \leq B_{j}$ A_j \le t_i \le B_j.

Якщо з кожною коровою можна з'єднати не більше однієї курки, а з кожною куркою — не більше однієї корови, допоможіть визначити максимально можливу кількість пар «корова — курка».

Вхідні дані

У першому рядку містяться $c (1 \leq c \leq 20000)$ c~(1 \le c \le 20000) та $n (1 \leq n \leq 20000)$ n~(1 \le n \le 20000). У наступних $c$ рядках містяться значення $t_{1}, \dots, t_{c}$ t_1, \ldots, t_c, а в наступних $n$ рядках — значення $A_{j}$ A_j та $B_{j} (A_{j} \leq B_{j})$ B_j~(A_j \le B_j) для $j = 1, \dots, n$ j = 1, \ldots, n. Значення $A_{j}, B_{j}$ A_j, B_j та $t_{i}$ t_i є невід'ємними цілими числами, що не перевищують $1 0^{9}$ 10^9, і не обов'язково різні.

Вихідні дані

Виведіть максимально можливу кількість пар «корова — курка».

Приклади

Приклад 1