22319_WrongAnswer

You are solving a crossword puzzle and you have already written down the answers to all questions. While filling in the answers in the diagram, you notice that some answers have overlapping letters that do not match, so you must have made some mistakes in the answers. Instead of checking your answers, you decide to write a computer program to find the maximum number of answers that could have been correct.

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

• One line with two integers H and V , satisfying 1 ≤ H, V ≤ 500: the number of horizontal and vertical words, respectively.

• H lines, one for each horizontal word, each with two integers x and y and a string W, satisfying 0 ≤ x, y ≤ 1,000 and 1 ≤ Length(W) ≤ 1,000: the location of the first letter and the answer.

• V lines, one for each vertical word, each with two integers x and y and a string W, satisfying 0 ≤ x, y ≤ 1,000 and 1 ≤ Length(W) ≤ 1,000: the location of the first letter and the answer.

Integers and strings on the same line are separated by single spaces. No pair of horizontal words will overlap, nor will any pair of vertical words. The words consist of upper case letters only.

The top left corner of the diagram is at x = y = 0, x runs in the horizontal direction, and y runs in the vertical direction (downwards).

For every test case in the input, the output should contain a single number, on a single line: the maximum number of answers that can fit in the crossword.

2
2 2
0 1 BAPC
0 2 LEIDEN
0 0 SOLUTION
2 1 WINNER
1 4
0 1 HELLO
1 0 HI
2 0 BYE
3 0 GOODBYE
4 0 FAREWELL

3
4

The first example below corresponds to the following diagram, where the (assumed) wrong answer is written in italics: