Copiado al portapapeles
Descripción
Estás resolviendo un crucigrama y ya has anotado las respuestas a todas las preguntas.
Al completar las respuestas en el diagrama, observas que algunas respuestas tienen letras superpuestas que no coinciden, por lo que debes haber cometido algunos errores en las respuestas. En lugar de verificar tus respuestas, decides escribir un programa de computadora para encontrar el número máximo de respuestas que podrían haber sido correctas.
Entrada
El primer numero contiene el numero de casos de prueba, cada caso tiene el siguiente formato:
Una linea con dos numeros 1 <= H, V <= 500 el numero de palabras horizontales y verticales respectivamente
H lineas, cada linea contiene dos numeros x, y que satisfacen 1 <= x, y <= 1000 y una cadena S, 1 <= longitud(S) <= 1000 son tus respuestas horizontales
V lineas, cada linea contiene dos numeros x, y que satisfacen 1 <= x, y <= 1000 y una cadena S, 1 <= longitud(S) <= 1000 son tus respuestas verticales
Los enteros y las cadenas estan separados por un solo espacio, ningun par de palabras horizontales se superponen, ningun par de palabras verticales se superponen
Solo se dara letras mayusculas
La esquina superior izquierda del crucigrama esta en la cordenada x = y = 0
Salida
Para cada caso de prueba en la entrada, la salida debe contener un solo número, en una sola línea: el número máximo de respuestas que pueden caber en el crucigrama.
Ejemplo Entrada
1 2 2 0 4 AUXILIATURA 0 5 ICPC 0 0 SOLUCION 3 4 ACM
Ejemplo Salida
3