Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2278
Fight for Food

Time Limit: 2 Seconds      Memory Limit: 32768 KB


I went into the Gate of Freedom with CX, and saw a sign saying "You may 'enjoy' your travel here, but first of all, you must get enough food! The only thing you can eat is rats!"


CX is very afraid of rats... So I must catch as many as possible!


There is an N * M (N, M<=10) filed, with rocks in it. A "." stands for an empty grid, a "#' stands for a rock, and an "L" stands for me - love_cx. Each time, I can move to an adjacent square, and if a rat appears in that grid at the same time, I can catch this rat.

How many rats I can catch at most?


This problem contains multiple test cases.

Each test case begins with two integers N and M. Next N lines contain the map. And then an integer P (P<=30000), stands for the number of rats. Next P lines, each line contain 3 numbers (x, y), T (T<=1,000,000,000). (x, y) is the location of the rat, and T is the time the rat appears. Catching is started at time 0. After the time a rat appears, it will disappear.


For each test case, output how many rats I can catch at most.

Sample Input

5 5
2 2 2
2 1 3
5 2 13
5 1 14

Sample Output


Contest: A Great Beloved and My Gate to Freedom
There is a cx, there is a love_cx.

Author: JIANG, Yanyan
Source: JIANG, Yanyan's Contest #2
Submit    Status