Римские цифры
Римские числа основаны на семи символах: "I", "V", "X", "L", "C", "D" и "M". Значения этих символов равны 1, 5, 10, 50, 100, 500 и 1000 соответственно. Чтобы определить десятичное значение римского числа, воспользуемся следующим алгоритмом:
Найдите самый значимый (наибольший по стоимости) символ. Если таких символов несколько, выберите самый левый. Пусть этот символ находится на позиции i.
Обозначим как Middle "стоимость" символа на позиции i.
Вычислите значение римского числа, образованного символами, стоящими справа от i. Обозначим это значение как Right.
Вычислите значение римского числа, образованного символами, стоящими слева от i. Обозначим это значение как Left.
Пусть Middle + Right – Left будет значением римского числа. Очевидно, что с помощью этого алгоритма одно и то же число можно записать различными способами. Например, число 19 можно записать как "IXX", "XIX", "XVIV", "XVIIII" и так далее.
Дано десятичное число n и римское число S. Ваша задача — найти такую перестановку символов S, которая будет представлять n в римской нотации.
Входные данные
Первая строка содержит целое число n в десятичной записи. Вторая строка содержит число S в римской записи (–50000 ≤ n ≤ 50000, 1 ≤ длина(S) ≤ 50).
Выходные данные
Первая строка выходного файла должна содержать римское число или слово "NO" (без кавычек), если решения нет.