多米诺骨牌移动

题目描述

有一个 $n \times m$ 的棋盘，其中 $n < 70$，$m < 70$，且 $n$ 和 $m$ 均为奇数。

棋盘的每个格子中都写有一个小写字母。

棋盘被 $\dfrac{n \times m - 1}{2}$ 个 $1 \times 2$ 的多米诺骨牌覆盖，只有左上角的格子没有被覆盖。

每次可以选择一个骨牌进行移动，规则如下：

• 横向骨牌只能横向移动；
• 纵向骨牌只能纵向移动；
• 移动后不能与其他骨牌发生重合。

现在要求让所有元音字母所在的位置都至少有一次没有被覆盖。

元音字母包括：

a, e, i, o, u, y

请问最少需要移动多少次。

输入格式

第一行包含两个整数 $N, M$，表示棋盘的行数和列数。

接下来 $N$ 行，每行包含 $M$ 个小写字母，表示棋盘上的字母矩形。

再接下来 $N$ 行，每行包含 $M$ 个字符，由 ., -, | 构成，表示初始骨牌覆盖状态：

• . 表示一个空位；
• 两个连续的 - 表示一个横向放置的骨牌；
• 两个上下相邻的 | 表示一个纵向放置的骨牌。

输出格式

输出一个整数，表示使所有元音字母所在位置都至少没有被覆盖一次所需的最少移动次数。

样例

样例输入 1

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

样例输出 1

2