IVXLCDM

Roman numerals are written with the seven letters I, V, X, L, C, D, and M, which stand for the values $1$, $5$, $10$, $50$, $100$, $500$, and $1000$ respectively. A number is written by placing these letters (repeated when necessary) from the largest value on the left to the smallest on the right. For example, $3$ is written III and $73$ is written LXXIII.

The exceptions are values whose units digit is $4$ or $9$, whose tens digit is $40$ or $90$, and whose hundreds digit is $400$ or $900$. These use the subtractive forms IV ($4$), IX ($9$), XL ($40$), XC ($90$), CD ($400$), and CM ($900$). For instance, $24$, $39$, $44$, $49$, and $94$ are written XXIV, XXXIX, XLIV, XLIX, and XCIV.

The following rules make every value have a unique representation:

• At most three consecutive I, X, or C may appear.
• Each of V, L, and D may appear at most once.
• Any number of M may appear.
• No other subtractive combinations are allowed (for example, IC for $99$ is forbidden).

In the Middle Ages the year a building was founded was often hidden in an inscription: some of its letters were emphasized, and reading only the emphasized letters in order spelled the year as a Roman numeral. For example, the inscription Matfyz is the best schooL In prague encodes MLI, that is, $1051$.

Over time an inscription may be damaged, so it is no longer known which letters were emphasized. Given only the plain text of an inscription, determine the latest year the building could have been founded — that is, the largest value of a valid Roman numeral that can be read as a subsequence of the inscription's letters (letter case is ignored). For example, from matfyz is the best school in prague one can read MCLI, that is, $1151$.

The input consists of one or more nonempty lines $l_1, \dots, l_n$. Each line contains only lowercase letters and spaces and has length at most $10{,}000$ characters. Read until the end of input.

For each line $l_i$, output a single line containing one integer: the largest value of a Roman numeral that can be encoded in $l_i$ by emphasizing some of its letters, or $0$ if no Roman numeral can be encoded.