Perché la mucca ha attraversato la strada (Argento)#10535
Le mucche di Farmer John stanno cercando di imparare ad attraversare la strada in modo sicuro ed efficiente. Ricordando la vecchia barzelletta "Perché la gallina ha attraversato la strada?", hanno deciso che le galline devono essere delle vere esperte nell'attraversare la strada, e sono andate in cerca di galline che potessero aiutarle.
Si scopre che le galline sono creature molto impegnate e hanno solo un tempo limitato per aiutare le mucche. Nella fattoria ci sono galline, numerate per comodità da a , e la gallina è disposta ad aiutare una mucca solo nel momento t_i. Le mucche, che non hanno fretta da nessuna parte, hanno un programma più flessibile. Nella fattoria ci sono mucche, numerate per comodità da a , e la mucca può attraversare la strada in qualsiasi momento compreso tra A_j e B_j inclusi.
Utilizzando un sistema di "compagni", ogni mucca vorrebbe trovare una gallina che la aiuti ad attraversare la strada. I loro programmi sono compatibili se è soddisfatta la condizione
A_j \le t_i \le B_j.
Se a ciascuna mucca può essere associata al massimo una gallina, e a ciascuna gallina al massimo una mucca, aiutateci a determinare il numero massimo possibile di coppie "mucca-gallina".
La prima riga contiene c~(1 \le c \le 20000) e n~(1 \le n \le 20000). Le successive righe contengono i valori t_1, \ldots, t_c, e le successive righe contengono i valori A_j e B_j~(A_j \le B_j) per j = 1, \ldots, n. I valori A_j, B_j e t_i sono numeri interi non negativi, non superiori a 10^9, e non necessariamente distinti.
Stampate il numero massimo possibile di coppie "mucca-gallina".
Esempio 1