Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum
2313.   IVXLCDM
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 182   Accepted Runs: 37


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.

Input Specification

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

Output Specification

For each line li 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 li, or 0 if no roman numeral can be encoded in it.

Sample Input

matfyz is the best school in prague
no year

Sample Output

1151
0


Source: CTU Open 2005
Submit   List    Runs   Forum   Statistics
Tianjin University Online Judge v1.2.4