Apples
By Cristhian Bonilha, UTFPR 
Brazil
By Cristhian Bonilha, UTFPR Brazil
Rafael decided to spend his weekend at his uncle's farm, Anthony, and when he realized that there was an apple tree there, he decided to make an apple pie.
To make the pie, however, Rafael would have to get as many apples as possible, and for that he decided to ask for help to his cousin. The deal was: His cousin would climb the tree and shake several branches containing apples, making them fall. As they would falling, Rafael would be on the ground with a basket and would get them between their travel from the tree to the ground. As the apples were falling fast, the impact with the ground would make them crack, and Rafael decided to ignore those apples that he couldn't get in time with his basket.
We can represent the situation as follows: Rafael is positioned in an area with N lines and M columns below the tree, and can move one position horizontally, vertically or diagonally by second. Each apple falls in a given position of this area, let's say [i, j] (i-th line, j-th column), and the exact moment that Rafael has to be at this position to get the apple is a given time t.
Given Rafael's initial position, count the maximum amount of apples he can get with his basket, between all the K apples felled by his cousin.
There will be several test cases. Each test case starts with three integers, N, M and K (3 ≤ N, M ≤ 20, 1 ≤ K ≤ 1000), representing, respectivelly, the amount of lines and columns of the area below the tree, and the number of apples fellen by his cousin.
Following there will be K lines, containing three integers each, Xi, Yi and Ti (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M, 1 ≤ Ti ≤ 2*K), representing, respectivelly, the line and column on which the i-th apple fell, and the exact time when Rafael has to be at such position to get the apple.
The sequence of Ti values given in the input is non-decreasing, in other words, Ti-1 ≤ Ti, for every 2 ≤ i ≤ K. There are no two apples that fall at the same position at the same time.
Following there will be two integers X and Y (1 ≤ X ≤ N, 1 ≤ Y ≤ M), indicating the line and the column on which Rafael is at time 0.
The last test case is indicated when N = M = K = 0, which should not be processed.
For each test case, print one line containing one integer, representing the maximum amount of apples Rafael can get with his basket.
| Sample Input | Sample Output |
|
5 5 3 |
3 |