M. Tomb Hater
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You've discovered the long-lost tomb of the great pharaoh T'om Bha Ter. After eluding a devious sequence of snake traps, boulder traps, ant traps, sand traps and speed traps, you've about had it with traps. Only one challenge remains between you and a hoard of priceless, museum-belonging-in artifacts. You enter a room from the North whose floor is a rectangular grid, each tile of which is inscribed with a glyph. A small plaque contains a list of glyph words (constructed from individual glyphs in a specified order) and the following brief set of instructions:

  1. From any given tile you may only move one tile to the South, West or East.
  2. You may not step on a tile more than once.
  3. The path you take must spell out a sequence of complete glyph words from the given list (repetition of glyph words is allowed).
  4. If multiple paths exist, you must find the path that steps on the least number of tiles.
Disobey any of these rules and you'll find yourself hurtling into a bottomless abyss. Since you brought your laptop, you immediately get to coding.
Input

Input starts with a line containing three positive integers $$$m$$$ $$$n$$$ $$$k$$$ ($$$ m,n,k \leq 50$$$), where $$$m$$$ and $$$n$$$ are the dimensions of the rectangular grid and $$$k$$$ is the number of glyph words. The next $$$m$$$ lines contain $$$n$$$ upper-case letters, separated by single spaces, representing the rectangular grid. The next $$$k$$$ lines each contain a glyph word, also consisting entirely of capital letters. Each glyph word will contain at most $$$50$$$ letters.

Output

If there is a route that starts at any Northernmost tile, ends at any Southernmost tile, and obeys all of the above rules, output the length of the shortest such route. Otherwise output impossible.

Examples
Input
3 4 1
X X P X
X X A T
X X X H
PATH
Output
4
Input
5 5 2
X X P X X
X X A T X
X X H H X
X M O X X
X E X X X
HOME
PATH
Output
8
Input
5 5 2
X X P X X
X X A T X
X X H X X
X M O X X
X E X X X
HOME
PATH
Output
impossible