STC06 - Keyboard

Byteman has received an extraordinary keyboard as a gift. The keyboard is a rectangle consisting of N rows and M columns with N*M keys placed on it. Moreover, all keys except the one in the top left corner are covered with domino tiles of size 1 x 2, so there are (N*M-1)/2 domino tiles in total. At any time, Byteman can move onto the free key one of the domino tiles adjacent to it by the shorter side. He can also press keys, but only if they are not covered.

Byteman would like to test (i.e., press) all the keys corresponding to vowels, that is, the letters aeiou or y. What is the minimum number of tile moves necessary to do that?

Input

The first line of the input contains two integers N and M (1 <= N,M < 70) that describe the dimensions of the keyboard. The next N lines contain M lowercase letters of the English alphabet each, describing the rows of the keyboard. Each of the next N lines contains M characters describing placement of the domino tiles: . (ASCII code 46) denotes an uncovered key, - (ASCII code 45) denotes a key covered by a domino tile placed horizontally and | (ASCII code 124) - a key covered by a tile placed vertically.

Output

If it is not possible for Byteman to press all the keys corresponding to vowels, your program should output just the single word "NIE" (i.e. no in Polish). Otherwise output the minimum number of tile moves that Byteman must make in order to press all the requested keys.

Example

For the input data:

3 3
ytr
hgf
dsa
.--
|||
|||

the correct result is:

2

Added by:Sergey Kulik
Date:2013-08-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ONTAK 2010

hide comments
2013-10-31 03:09:33 Jacob Plachta
To clarify, there might be multiple keys with the same letter - so, more than 6 keys might need to be pressed.
2013-08-18 06:22:24 ramprakash_k
is y also to be considered as vowel?

(answer): in Polish, it is. the source is ONTAK - one of the Polish IOI training camps. so you should consider y vowel in order to get AC

Last edit: 2013-08-18 07:36:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.