Римські числа

Дано рядок, який складається з символів 'I', 'V', 'X', 'L', 'C', 'D' та 'M'. Вам потрібно розбити цей рядок на кілька сегментів так, щоб кожен сегмент був правильним римським числом, а сума цих чисел була мінімальною.

Правильний римський числівник будується так. Спочатку символ 'M' записується стільки разів, скільки в числі тисяч. Наприклад, число $2045$ містить дві тисячі, тож його римський запис починається з "MM". Потім береться залишок від ділення на $1000$. В залежності від кількості сотень у залишку додається: "C" для однієї сотні, "CC" для двох, "CCC", "CD", "D", "DC", "DCC", "DCCC", або "CM" для трьох, чотирьох, ..., до дев'яти сотень відповідно. Для $2045$ залишок — $45$, сотень немає, тому нічого не додається.

Потім береться залишок від ділення на $100$. Залежно від кількості десятків додається "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", або "XC" (або нічого, якщо десятків немає). Для $2045$ додається "XL".

Далі береться залишок від ділення вихідного числа на $10$. В залежності від цього додається "I", "II", "III", "IV", "V", "VI", "VII", "VIII" або "IX" для $1$, $2$, ..., $9$ відповідно. Якщо залишок нуль, нічого не додається. Для $2045$ додається "V".

Таким чином, римське число для $2045$ — "MMXLV".

Окрім того, існує обмеження: жодний символ не може з'являтися у римському числі більше трьох разів поспіль. Тому правильні римські числа існують лише для чисел від $1$ до $3999$ включно.