One ancient Roman merchant took a loan several times from an ancient Roman bank. Each time the banker wrote down the amount of the loan on a piece of parchment using Roman numerals. But due to the high cost of parchment, the recording was made tightly and all the numbers turned out to be written in a row, without separators. When the merchant came to return the loan, it turned out that it was impossible to set the split of the record into numbers.
For example, if the string "XIIV" is written on parchment, it can be divided into Roman numbers in different ways, for example, XI + IV = 11 + 4 = 15 or XII + V = 12 + 5 = 17, other splitting options are possible.
The merchant wants to return as little money as possible, so he wants to split the string of numbers into Roman numbers in such a way that the sum of all numbers is as small as possible.
The program receives a string as input, the length of which does not exceed 250 characters. The string consists only of capital Latin letters I, V, X, L, С, D, M.
The program should output a single number – the minimum possible sum that can be obtained by splitting the given string into a sequence of valid Roman numerals. The answer must be printed in Arabic numerals in the decimal number system.
Rules for Roman numerals
Roman numerals can be written as integers from 1 to 3999. The number is represented as the sum of thousands, hundreds, tens and units. Further, one element is taken from the following table, corresponding to thousands, hundreds, tens, units in exactly that order.
If the number of thousands, hundreds, tens, units is 0, then nothing is taken from the corresponding column. For example, the number 1990 is written as 1000 + 900 + 90 = MCMXC.