"Roman" dəhlizi
Roma rəqəmlərinin simvollarını xatırlayaq. Bu simvollar 1 -dən 3999-a qədər olan təbii ədədləri ifadə etmək üçün istifadə olunur. Böyük Latın hərfləri 'I', 'V', 'X', 'L', 'C', 'D', 'M' və onların kombinasiyaları atom ədədləri adlanan ədədləri təmsil edir (aşağıdakı cədvələ baxın).
Bir N ədədini yazmaq üçün, N-dən böyük olmayan ən böyük atom ədədini K tapmaq lazımdır. Tapılan K ədədinin Roma simvolu yazılır və bu proses (N-K) üçün təkrarlanır.
Roma rəqəmləri boşluqsuz soldan sağa yazılır. Məsələn, 999 ədədinin Roma simvolu CMXCIX-dir (bəziləri IM düşünə bilər).
Düzbucaqlı bir dəhlizdən keçməlisiniz. Dəhliz n metr enində və m metr uzunluğundadır (1 ≤ n, m ≤ 15, n*m ≤ 100). O, kvadrat plitələrlə döşənib. Hər bir plitə 1 metr enindədir və üzərində 'Roma' simvolu var: 'I', 'V', 'X', 'L', 'C', 'D' və ya 'M'. Dəhlizdən keçərkən bir plitədən digərinə keçirsiniz. Cari plitədən yalnız şaquli və ya üfüqi bitişik plitələrə keçə bilərsiniz (diagonal yox). Sol tərəfdən başlayıb sağ tərəfdə bitirirsiniz (aşağıdakı şəkilə baxın).
Dəhlizdən keçə bilərsinizmi ki, yolunuzu təşkil edən plitələr üzərindəki simvolların ardıcıllığı Roma rəqəmlərində düzgün ədəd olsun? Bütün mümkün həllər arasında minimal ədədi tapmalısınız.
Giriş verilənləri
Giriş məlumatları birinci sətirdə bir və ya daha çox boşluqla ayrılmış n və m ədədlərini ehtiva edir. Növbəti n sətirin hər biri plitələri təsvir edən m simvoldan ibarətdir.
Çıxış verilənləri
Çıxış faylı tapılan Roma ədədini və ya tələb olunan şəkildə dəhlizdən keçmək mümkün deyilsə NO sözünü ehtiva edən bir sətir ehtiva edir.