“Романський” коридор
Нагадаємо позначення римських чисел. Вони використовуються для натуральних чисел від 1 до 3999. Великі латинські літери 'I', 'V', 'X', 'L', 'C', 'D', 'M' та їх комбінації представляють так звані атомарні числа (див. таблицю нижче).
Щоб записати число N, потрібно знайти найбільше атомарне число K, яке не перевищує N. Римське позначення знайденого числа K записується, і процес повторюється для (N-K).
Римські числа записуються зліва направо без пробілів. Наприклад, число 999 у римському позначенні є CMXCIX (але не IM, як хтось може подумати).
Вам потрібно пройти через прямокутний коридор. Коридор має ширину n метрів і довжину m метрів (1 ≤ n, m ≤ 15, n*m ≤ 100). Він викладений квадратними плитками. Кожна плитка має ширину 1 метр і на ній зображено 'римський' символ: 'I', 'V', 'X', 'L', 'C', 'D' або 'M'. Проходячи коридором, ви рухаєтеся з однієї плитки на іншу. З поточної плитки ви можете рухатися лише на одну з сусідніх плиток, вертикально або горизонтально (але не по діагоналі). Ви починаєте зліва і закінчуєте справа (див. малюнок нижче).
Чи можете ви пройти через коридор так, щоб послідовність символів на плитках, що складають ваш шлях, була правильним числом у римському позначенні? Серед усіх можливих рішень вам потрібно знайти мінімальне число.
Вхідні дані
Вхідні дані у першому рядку містять числа n і m, розділені одним або кількома пробілами. Кожен з наступних n рядків складається з m символів, що описують плитки.
Вихідні дані
Вихідний файл містить один рядок із знайденим римським числом або слово NO, якщо неможливо пройти через коридор у потрібний спосіб.