Planting Trees in an Orchard

You are given an orchard represented as a grid with n rows and m columns. Each cell in the grid is either free (denoted by .) or blocked by an obstacle (denoted by #). You also have a set of tree types, where each tree type is described by three integers: width w, height h, and an extra parameter c (which can be ignored for the purpose of planting decision). A tree of size \(w \times h\) can be planted at position \((x,y)\) if and only if for every \(0 \le i < h\) and \(0 \le j < w\) the cell \((x+i, y+j)\) is free (i.e. contains a dot).

Your task is to determine the maximum number of different tree types that can be planted in the orchard without overlapping obstacles or previously planted trees. For each tree type, you can choose to plant it at one valid location or skip planting it.

inputFormat

The input is read from standard input and has the following format:

 n m
 row_1
 row_2
 ...
 row_n
 t
 w1 h1 c1
 w2 h2 c2
 ...
 wt ht ct

Here, the first line contains two integers \(n\) and \(m\). The next \(n\) lines each contain a string of \(m\) characters (either . or #) representing the orchard. Following that, an integer \(t\) denotes the number of tree types. Each of the next \(t\) lines contains three integers representing the width, height, and an extra parameter (which does not affect planting) of a tree type.

outputFormat

Output a single integer to standard output which is the maximum number of tree types that can be planted in the orchard following the rules.

5 5
.....
..#..
.....
..#..
.....
3
2 2 1
3 1 2
1 2 1

3