Roman numerals
The given string is composed of the characters 'I', 'V', 'X', 'L', 'C', 'D', and 'M'. Your task is to divide this string into several segments, where each segment forms a valid Roman numeral, such that the total sum of these numerals is minimized.
A valid Roman numeral follows these rules: First, the symbol 'M' is used to represent thousands. For instance, the number 2045 has two thousands, so it begins with "MM". Next, you take the remainder when divided by 1000. Based on the number of hundreds in this remainder, you add the following to the Roman numeral: "C" for one hundred, "CC" for two, "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" for three, four, ..., up to nine hundred. For 2045, the remainder is 45, which has no hundreds, so nothing is added.
Then, take the remainder when divided by 100. Depending on the number of tens, the Roman numeral is extended with "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", or "XC". For 2045, you add "XL".
Finally, take the remainder when divided by 10. Based on this, add "I", "II", "III", "IV", "V", "VI", "VII", "VIII", or "IX" for 1 to 9, or nothing if the remainder is zero. For 2045, you add "V".
Thus, the Roman numeral for 2045 is "MMXLV".
Additionally, Roman numerals cannot have any symbol repeated more than three times consecutively. Therefore, valid Roman numerals are only those representing numbers from 1 to 3999.
Input
The input consists of a single non-empty string with a maximum length of 20000 characters, containing only the specified uppercase Latin letters ('I', 'V', 'X', 'L', 'C', 'D', and 'M').
Output
Output a single number representing the minimum possible sum of the numbers.