Walk the Talk

A farmer has laid out an $H \times W$ grid of uppercase letters ($1 \le H \le 30$, $1 \le W \le 30$). A cow spells a word by hopping from square to square and reading the letters in the order she visits them.

She may start on any square. From her current square she may only hop to a square that lies to the right and/or above it — never to a square that is to the left or lower. The first row of the grid is the top row, so "above" means a smaller row number. A single hop may span any distance, since the cows are world-class jumpers.

A path is the exact sequence of squares a cow visits. A path may consist of a single square, which spells the one-letter word written on it. Because every hop moves strictly to the right and/or strictly up, a path never repeats a square. Two different paths may spell the same word, but no two cows may follow the exact same path.

You are given the grid and a list of valid words. A path spells a word when the letters read along it, in visiting order, exactly equal that word. Count how many distinct paths spell some word from the list. Because every cow must take a different path, this count is the greatest number of cows that can enter.

For intuition: to spell TO, a cow standing on a T may hop to any O that is in the same row to its right, or in a higher row (to the right, directly above, or up-and-to-the-right). She can never reach an O that lies to her left or below.

• Line 1: two integers $H$ and $W$.
• Lines 2 through $H+1$: each line has $W$ uppercase letters (A–Z) with no spaces and gives one grid row. The first of these lines is the top row; the first character of a line is its left-most square.
• Line $H+2$: an integer $N$ ($N \ge 1$), the number of valid words.
• Next $N$ lines: one valid word per line, each made of uppercase letters (A–Z). Repeated words are treated as a single word.

• One line with a single integer: the number of distinct paths that spell a word from the list (equivalently, the maximum number of cows that can enter without any two sharing a path).