6667번 - IVXLCDM 다국어

Roman numerals are represented by a string consisting of characters "I", "V", "X", "L", "C", "D" and "M". These symbols represent the decimal values 1, 5, 10, 50, 100, 500 and 1000, respectively. To represent other values, these symbols, and multiples where necessary, are concatenated, with the smaller-valued symbols written further to the right. For example, the number 3 is represented as "III", and the value 73 is represented as "LXXIII". The exceptions to this rule occur for numbers having units values of 4 or 9, tens values of 40 or 90, and hundreds values of 400 and 900. For these cases, the Roman numeral representations are "IV" (4), "IX" (9), "XL" (40), "XC" (90), "CD" (400) and "CM" (900). So the Roman numeral representations for 24, 39, 44, 49, and 94 are "XXIV", "XXXIX", "XLIV", "XLIX", and "XCIV", respectively. Note that at most three consecutive characters "I", "X" or "C" may appear in the numeral, and each numeral contains characters "V", "L" and "D" at most once, but arbitrarily many "M"'s may appear in it. Also, it is forbidden to use, e.g., "IC" for 99.

In middle-ages, the year a building was constructed was often indicated in an inscription: some of the characters in the inscription were emphasized, and when these characters were concatenated, they formed the number of the year in roman numerals. For example, a building with inscription "Matfyz is the best schooL In prague" was clearly founded in year "MLI", i.e., 1051. However, the inscription often gets damaged and it is no longer clear which of the letters were emphasized. The archaeologists would in that case like to know at least the latest date in that the building could be constructed, by determining the largest numeral that can be encoded in an inscription in this way. For example, if they find an inscription "matfyz is the best school in prague", they know that the building was founded at latest in year "MCLI", i.e., 1151.

The input consists of several nonempty lines l₁,..., l_n. Each of the lines consists of lowercase letters and spaces. The length of each line is at most 10 000 characters.

For each line l_i of the input, write a line consisting of a single integer to the output. This integer must be the largest roman numeral that can be encoded in the inscription given by l_i, or 0 if no roman numeral can be encoded in it.