Roman numerals

The given string consists of the characters 'I', 'V', 'X', 'L', 'C', 'D', and 'M'. You are to split this string into several segments so that each segment is a valid Roman numeral, and the sum of these numerals is minimized.

A valid Roman numeral is formed as follows. First, the symbol 'M' is written as many times as there are whole thousands in the number. For example, the number $2045$ has two thousands, so its Roman numeral begins with "MM". Then, take the remainder after dividing by $1000$. Based on the number of hundreds in this remainder, you add: "C" for one hundred, "CC" for two, "CCC", "CD", "D", "DC", "DCC", "DCCC", or "CM" for three, four, ..., up to nine hundred, respectively. For $2045$, the remainder is $45$, which has no hundreds, so nothing is added.

Next, take the remainder after dividing by $100$. According to the number of tens, add "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", or "XC" (or nothing, if there are no tens). For $2045$, add "XL".

Then, take the remainder after dividing the original number by $10$. Based on this, add "I", "II", "III", "IV", "V", "VI", "VII", "VIII", or "IX" for $1$, $2$, ..., $9$ respectively. If the remainder is zero, add nothing. For $2045$, you add "V".

Thus, the Roman numeral for $2045$ is "MMXLV".

Additionally, there is the restriction that no symbol may appear more than three times in a row in Roman numerals. Therefore, valid Roman numerals exist only for numbers from $1$ to $3999$ inclusive.