로마 숫자 복도

로마 숫자는 $1$부터 $3999$까지의 자연수를 나타냅니다. 대문자 라틴 문자 I, V, X, L, C, D, M을 사용하며, 각 "기본" 값은 아래 표와 같습니다.

수 $N$을 적으려면, $N$을 넘지 않는 가장 큰 기본 값 $K$를 골라 그 로마 표기를 이어 붙이고, 남은 $N - K$에 대해 같은 과정을 반복합니다. 기호는 공백 없이 왼쪽에서 오른쪽으로 적습니다. 예를 들어 $999$는 (IM이 아니라) CMXCIX로 적습니다.

당신은 폭이 $n$미터, 길이가 $m$미터인 직사각형 복도를 지나가야 합니다 ($1 \le n, m \le 15$, $n \times m \le 100$). 복도는 한 변이 1미터인 정사각형 타일로 덮여 있고, 각 타일에는 로마 기호 I, V, X, L, C, D, M 중 하나가 적혀 있습니다. 당신은 타일에서 타일로 이동하며, 현재 타일에서 변을 맞대고 있는 타일(위, 아래, 왼쪽, 오른쪽 — 대각선은 불가)로만 한 칸씩 움직일 수 있습니다. 출발은 가장 왼쪽 열에서 하고, 도착은 가장 오른쪽 열에서 해야 합니다.

이동 경로를 따라 처음부터 끝까지 타일의 기호를 읽으면 하나의 문자열이 만들어집니다. 그 문자열이 올바른 로마 숫자가 되는 경로를 찾고, 그러한 모든 경로 중에서 값이 가장 작은 것을 구하세요. 올바른 로마 숫자를 만드는 경로가 하나도 없다면 불가능하다고 답합니다.

첫째 줄에는 두 정수 $n$과 $m$이 하나 이상의 공백으로 구분되어 주어집니다. 이어지는 $n$개의 줄에는 각각 타일 한 행을 나타내는 $m$개의 문자가 주어집니다.

가장 왼쪽 열에서 가장 오른쪽 열까지 이어지는 경로로 만들 수 있는, 값이 가장 작은 올바른 로마 숫자를 출력합니다. 그러한 경로가 없으면 NO를 출력합니다.