Longest Valid Path in a Letter Grid

You are given a grid of letters of size \(H \times W\) and a dictionary containing a set of words. Your task is to find the length of the longest path in the grid that forms a valid word contained in the dictionary. A path is defined as a sequence of cells where each cell is adjacent to the previous one (up, down, left, or right), and each cell in the path may be used at most once.

More formally, if the grid is represented as \(G\) and the dictionary as \(D\), then a valid path consists of indices \((i_1, j_1), (i_2, j_2), \ldots, (i_k, j_k)\) such that for every \(1 \leq t < k\), the cells \((i_t, j_t)\) and \((i_{t+1}, j_{t+1})\) are adjacent. The word formed by this path is \(G[i_1][j_1]G[i_2][j_2]\ldots G[i_k][j_k]\). Your goal is to maximize \(k\) with the constraint that the formed word belongs to \(D\).

inputFormat

The input is read from standard input (stdin) and consists of the following:

1. Two integers (H) and (W) representing the number of rows and columns in the grid.
2. (H) lines each containing a string of length (W) representing the grid.
3. An integer (N), the number of words in the dictionary.
4. (N) lines, each containing a word.

All values are separated by spaces or newline characters.

outputFormat

Output a single integer to standard output (stdout): the maximum length of a valid word that can be formed from a path in the grid. If no valid word can be formed, output 0.## sample

3 3
aaa
aba
aaa
4
aaa
aba
aaaa
abaa

4