Fight for Food

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Background

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!

Problem

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?

Input

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.

Output

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

Sample Input

5 5
L....
..#..
###.#
#....
#.###
4
2 2 2
2 1 3
5 2 13
5 1 14

Sample Output

3

Submit

Source: JIANG, Yanyan's Contest #2