El granjero John está expandiendo su granja! Ha identificado la ubicación perfecta: el Bosque Rojo-Negro, que consta de ~N~ árboles en una línea numérica, con el árbol ~i~ en la posición ~x_i~. Las leyes de protección ambiental restringen qué árboles puede talar el granjero John para hacer espacio para su granja. Hay ~K~ restricciones que especifican que debe haber al menos ~t_i~ árboles en el segmento de línea ~[l_i,r_i]~, incluyendo los puntos finales. Se garantiza que el Bosque Rojo-Negro inicialmente cumple con estas restricciones.

Entrada

Cada entrada consiste en ~T~ casos de prueba independientes. Se garantiza que la suma de todos los ~N~ y la suma de todos los ~K~ dentro de una entrada no exceden ~3 \cdot 10^5~.

La primera línea de la entrada contiene ~T~. Luego, cada caso de prueba está formateado de la siguiente manera:

• La primera línea contiene los enteros ~N~ y ~K~. La siguiente línea contiene los ~N~ enteros ~x_1, \ldots,x_N~. Cada una de las siguientes ~K~ líneas contiene tres enteros separados por espacios: ~l_i, r_i~ y ~t_i~.

Salida

Para cada caso de prueba, imprime una línea con un entero que indique el número máximo de árboles que el granjero John puede talar.

Restricciones

• ~1 \leq N \leq 10^5~
• ~-10^9 \leq x_i \leq 10^9~
• ~1 \leq K \leq 10^5~
• ~-10^9 \leq l_i,r_i \leq 10^9~
• ~1 \leq T \leq 10~

Ejemplo de Entrada

3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4

Ejemplo de Salida

4
4
3

• Para el primer caso de prueba, el granjero John puede talar los primeros 4 árboles, dejando los árboles en ~x_i=2,6,7~ para cumplir con la restricción.
• Para el segundo caso de prueba, la restricción adicional no afecta qué árboles puede talar el granjero John, por lo que puede talar los mismos árboles y cumplir con ambas restricciones.
• Para el tercer caso de prueba, el granjero John solo puede talar como máximo 3 árboles porque inicialmente hay 7 árboles, pero la segunda restricción le exige dejar al menos 4 árboles sin cortar.

Calificación

Entradas	Restricciones adicionales
2	~N, K \leq 16~
3-5	~N, K \leq 1000~
6-7	~t_i = 1~ para todo ~i = 1, \dots, K~
8-11	Sin restricciones adicionales

USACO 2024 December Contest, Silver Problem 2. Deforestation.