Дистанционный практикум по программированию

Как известно, римские числа записываются знаками (цифрами): «I», «V», «X», «L», «C», «D» и «M». «Вес» этих знаков, соответственно, равен 1, 5, 10, 50, 100, 500 и 1000.

Для вычисления значения римского числа будем использовать следующий алгоритм:

1.     Если запись римского числа есть пустая строка, то число считается равным 0, иначе выполняем пункты 2-6.

2.     В записи числа найдем самую значащую (самую большую по весу) цифру; если таких цифр несколько, то возьмем самую левую из них. Пусть найденная цифра стоит в позиции i.

3.     Обозначим через Main вес цифры, стоящей в позиции i.

4.     По правилам 1-6 вычислим величину римского числа, образованного только цифрами, стоящими правее i. Обозначим эту величину как Right.

5.     По правилам 1-6 вычислим величину римского числа, образованного только цифрами, стоящими левее i. Обозначим эту величину как Left.

6.     Определим величину всего римского числа как Main + Right – Left.

Очевидно, что если использовать данный алгоритм, то одно и тоже число n можно записать множеством способов. Например, число n=19 можно записать как «IXX», «XIX», «XVIV», «XVIIII» и так далее.

Напишите программу, которая по заданной строке римских цифр S, определит, можно ли, используя все эти цифры (с учетом их кратности), построить римскую запись числа n.

Ограничения

В строке S используется не более 50 римских цифр.

–50000 <= n <= 50000.

Входные данные

Первая строка входного файла содержит целое десятичное число n. Вторая строка входного файла содержит строку римских цифр S.

Выходные данные

Единственная строка выходного файла должна содержать римскую запись десятичного числа n из римских цифр строки S или слово «NO» (без кавычек), если римская запись не существует.

Примеры

Input	Output
16 XXVI	XVXI

 

Input	Output
15 XXVI	NO