Римская запись с выбором
Строка состоит из цифр римской системы счисления — заглавных латинских букв I, V, X, L, C, D, M. Найдите последовательность из максимального количества идущих подряд символов, которая представляет собой корректную римскую запись числа от 1 до 3999. Если найдено несколько таких последовательностей, выберите ту, которая обозначает наименьшее число. Последовательности могут перекрываться.
Корректная запись составляется слева направо из тысяч, сотен, десятков и единиц. Тысячи: пусто, M, MM, MMM. Сотни: пусто, C, CC, CCC, CD, D, DC, DCC, DCCC, CM. Десятки: пусто, X, XX, XXX, XL, L, LX, LXX, LXXX, XC. Единицы: пусто, I, II, III, IV, V, VI, VII, VIII, IX. Хотя бы один разряд должен быть непустым.
Числовые значения цифр: I — 1, V — 5, X — 10, L — 50, C — 100, D — 500, M — 1000. В парах IV, IX, XL, XC, CD и CM значение меньшей цифры вычитается, остальные значения складываются.
Входные данные
Во входных данных содержится одна непустая строка длиной не более символов.
Выходные данные
Выведите одно число — десятичное значение найденной последовательности римских цифр.
Примеры
MMXXVI
2026
XXLIII
43
Примечание
В первом примере подходит вся строка: MMXXVI обозначает число 2026. Во втором примере вся строка не является корректной записью, но со второго символа начинается запись XLIII числа 43.