SP15573 STC06 - Keyboard

Byteman 收到了一个特别的键盘作为礼物。这个键盘是一个 $N$ 行 $M$ 列的矩形，一共排布着 $N \times M$ 个按键。除了左上角的按键外，其余的按键都被 $1 \times 2$ 的多米诺骨牌覆盖，总共有 $(N \times M - 1) / 2$ 个多米诺骨牌覆盖在上面。Byteman 可以将相邻的多米诺骨牌（靠短边相邻）移动到空着的按键上。他也可以按下未被骨牌覆盖的按键。 Byteman 想要测试键盘上所有元音字母（a, e, i, o, u 或 y）对应的按键。请问他最少需要移动多少次多米诺骨牌才能做到？

第一行包含两个整数 $N$ 和 $M$，分别表示键盘的行数和列数 ($1 \le N, M < 70$)。接下来的 $N$ 行，每行包含 $M$ 个小写字母，描述了键盘上的字符排列情况。然后是另 $N$ 行，每行同样包含 $M$ 个字符，表示多米诺骨牌的覆盖情况：`.` 表示按键未被覆盖，`-` 表示按键被水平放置的骨牌覆盖，`|` 表示按键被垂直放置的骨牌覆盖。

如果 Byteman 无法按下所有代表元音字母的按键，请输出 `NIE`（即波兰语的“不”）。若可以请输出 Byteman 为按下所有请求按键所进行的最少多米诺骨牌移动次数。 ## 示例 ### 输入 ``` 3 3 ytr hgf dsa .-- ||| ||| ``` ### 输出 ``` 2 ``` **本翻译由 AI 自动生成**