¿Por qué la vaca cruzó la carretera?

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Las vacas del Granjero Juan están tratando de aprender a cruzar la carretera bien. Recordando el viejo cuento "¿porqué el pollo cruzo la carretera?", ellas piensan que los pollos son expertos cruzando la carretera, y van en busca de los pollos para que las ayuden.

Sucede que los pollos son criaturas muy ocupadas y tienen tiempo limitado para ayudar a las vacas. Hay $C$ ~C~ polos en la granja (convenientemente numerados $1 \ldots C$ ~1 \ldots C~, y cada pollo $i$ ~i~ está dispuesto a ayudar a una vaca precisamente en el tiempo $T_i$ ~T_i~. Las vacas, nunca apuradas, tienen más flexibilidad en sus horarios. Hay $N$ ~N~ vacas en la granja, convenientemente numeradas $1...N$ ~1...N~, donde la vaca $j$ ~j~ puede cruzar la carretera entre el tiempo $A_j$ ~A_j~ y el tiempo $B_j$ ~B_j~. Pensando que el "sistema compañero" es la mejor manera de proceder, cada vaca $j$ ~j~ quisiera idealmente encontrar un pollo $i$ ~i~ que la ayude a cruzar la carretera; para que sus horarios sean compatible $i$ ~i~ y $j$ ~j~ deben satisfacer $A_j \leq T_i \leq B_j$ ~A_j \leq T_i \leq B_j~.

Si cada vaca puede ser asociada con a lo más un pollo y cada pollo con a lo más una vaca, por favor, ayude a calcular el máximo número de parejas pollo-vaca que puede ser construido.

Entrada

La primera línea de la entrada contiene $C$ ~C~ y $N$ ~N~. Las siguientes $C$ ~C~ líneas contienen $T_1...T_C$ ~T_1...T_C~, y las siguientes $N$ ~N~ líneas contienen $A_j$ ~A_j~ y $B_j$ ~B_j~ $(A_j \leq B_j)$ ~(A_j \leq B_j)~ para $j = 1 \ldots N$ ~j = 1 \ldots N~. Los A′s, B′s, y T$'s son todos enteros no negativos (no necesariamente distintos) de tamaño a lo más $1,000,000,000$ ~1,000,000,000~.