키보드

바이트맨(Byteman)이 특이한 키보드를 선물로 받았다. 이 키보드는 $n$개의 행과 $m$개의 열로 이루어진 직사각형이며, 모두 $n \times m$개의 키가 놓여 있다. 왼쪽 위 모서리에 있는 키 하나를 제외한 모든 키는 크기가 $1 \times 2$인 도미노 타일로 덮여 있다. 따라서 타일은 모두 $(n \times m - 1)/2$개이고, 덮이지 않은 키는 정확히 하나뿐이다.

바이트맨은 언제든지, 짧은 변이 비어 있는 키에 닿아 있는 타일 하나를 골라 그 빈 키 쪽으로 한 칸 밀 수 있다. 밀고 나면 그 타일이 방금 전까지 비어 있던 키를 덮고, 타일의 반대쪽 끝에 있던 키가 새로 비게 된다. 키는 덮여 있지 않을 때에만 누를 수 있다.

바이트맨은 모음, 즉 a, e, i, o, u, y 중 하나가 적힌 모든 키를 눌러 보고 싶다. 이를 위해 필요한 타일 이동 횟수의 최솟값을 구하여라.

첫째 줄에 키보드의 크기를 나타내는 두 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 70$).

다음 $n$개의 줄에는 각각 $m$개의 영어 소문자가 주어지며, 키보드의 각 행에 적힌 글자를 나타낸다.

그다음 $n$개의 줄에는 각각 $m$개의 문자가 주어지며, 타일이 놓인 상태를 나타낸다. 마침표 .는 덮이지 않은 키를, 붙임표 -는 가로로 놓인 타일에 덮인 키를, 세로줄 |는 세로로 놓인 타일에 덮인 키를 뜻한다.

모든 모음 키를 누르는 것이 불가능하면 NIE(폴란드어로 '아니오')라는 한 단어를 출력한다. 가능하다면 모든 모음 키를 누르기 위해 필요한 타일 이동 횟수의 최솟값을 출력한다.