"Романський" коридор

Нагадаємо позначення римських чисел. Вони використовуються для натуральних чисел від $1$ до $3999$. Великі латинські літери 'I', 'V', 'X', 'L', 'C', 'D', 'M' та їх комбінації представляють так звані атомарні числа (див. таблицю нижче).

Щоб записати число $N$, потрібно знайти найбільше атомарне число $K$, яке не перевищує $N$. Римське позначення знайденого числа $K$ записується, і процес повторюється для (N-K).

Римські числа записуються зліва направо без пробілів. Наприклад, число $999$ у римському позначенні є CMXCIX (але не IM, як хтось може подумати).

Вам потрібно пройти через прямокутний коридор. Коридор має ширину $n$ метрів і довжину $m$ метрів (1 \le n, m \le 15, n \cdot m \le 100). Він викладений квадратними плитками. Кожна плитка має ширину $1$ метр і на ній зображено 'римський' символ: 'I', 'V', 'X', 'L', 'C', 'D' або 'M'. Проходячи коридором, ви рухаєтеся з однієї плитки на іншу. З поточної плитки ви можете рухатися лише на одну з сусідніх плиток, вертикально або горизонтально (але не по діагоналі). Ви починаєте зліва і закінчуєте справа (див. малюнок нижче).

Чи можете ви пройти через коридор так, щоб послідовність символів на плитках, що складають ваш шлях, була правильним числом у римському позначенні? Серед усіх можливих рішень вам потрібно знайти мінімальне число.