Roman Corridor

Roman numerals represent the natural numbers from $1$ to $3999$. They use the capital Latin letters I, V, X, L, C, D, M, whose "atomic" values are shown below.

To write a number $N$, repeatedly take the largest atomic value $K$ that does not exceed $N$, append its Roman form, and continue with $N - K$. The symbols are written left to right with no spaces. For example, $999$ is written as CMXCIX (not IM, as one might guess).

You must walk through a rectangular corridor that is $n$ meters wide and $m$ meters long ($1 \le n, m \le 15$, $n \times m \le 100$). It is paved with square tiles, one meter on a side, and every tile shows one Roman symbol: I, V, X, L, C, D, or M. You move from tile to tile; from the current tile you may step only to a tile that shares an edge with it (up, down, left, or right — never diagonally). You enter from the leftmost column and must leave from the rightmost column.

Reading the symbols along your route from start to finish yields a string. Find a route whose string is a valid Roman numeral, and among all such routes report the one with the smallest value. If no route spells a valid Roman numeral, report that it is impossible.

The first line contains two integers $n$ and $m$, separated by one or more spaces. Each of the next $n$ lines contains $m$ characters describing one row of tiles.

Print the smallest valid Roman numeral that can be spelled by a route from the leftmost column to the rightmost column. If no such route exists, print NO.