IVXLCDM

로마 숫자는 일곱 개의 문자 I, V, X, L, C, D, M으로 표기하며, 각각 $1$, $5$, $10$, $50$, $100$, $500$, $1000$을 나타낸다. 수를 표기할 때는 값이 큰 문자를 왼쪽에, 값이 작은 문자를 오른쪽에 두고 필요하면 문자를 반복한다. 예를 들어 $3$은 III, $73$은 LXXIII로 쓴다.

예외는 일의 자리가 $4$ 또는 $9$, 십의 자리가 $40$ 또는 $90$, 백의 자리가 $400$ 또는 $900$인 경우이며, 이때는 빼기 표기 IV($4$), IX($9$), XL($40$), XC($90$), CD($400$), CM($900$)를 사용한다. 예를 들어 $24$, $39$, $44$, $49$, $94$는 각각 XXIV, XXXIX, XLIV, XLIX, XCIV로 쓴다.

다음 규칙에 따라 모든 값은 유일한 표기를 가진다.

• I, X, C는 연속해서 최대 세 번까지 나올 수 있다.
• V, L, D는 각각 최대 한 번만 나올 수 있다.
• M은 몇 번이든 나올 수 있다.
• 위에 나열한 것 외의 빼기 표기는 허용되지 않는다(예를 들어 $99$를 IC로 쓰는 것은 금지된다).

중세에는 건물이 세워진 연도를 비문에 숨겨 두는 일이 많았다. 비문의 일부 글자를 강조한 뒤 강조된 글자만 순서대로 읽으면 로마 숫자로 된 연도가 되었다. 예를 들어 비문 Matfyz is the best schooL In prague에서 강조된 글자를 읽으면 MLI, 즉 $1051$이 된다.

세월이 흐르면 비문이 손상되어 어떤 글자가 강조되어 있었는지 알 수 없게 되기도 한다. 비문의 원문만 주어졌을 때, 그 건물이 세워졌을 수 있는 가장 늦은 연도, 즉 비문의 글자들을 부분 수열로 읽어 만들 수 있는 유효한 로마 숫자의 최댓값을 구하여라. 이때 글자의 대소문자는 구분하지 않는다. 예를 들어 matfyz is the best school in prague에서는 MCLI, 즉 $1151$을 읽어낼 수 있다.

입력은 하나 이상의 비어 있지 않은 줄 $l_1, \dots, l_n$으로 이루어진다. 각 줄은 소문자 알파벳과 공백으로만 이루어지며, 길이는 최대 $10{,}000$자이다. 입력의 끝까지 처리한다.

각 줄 $l_i$에 대해, 그 줄의 일부 글자를 강조하여 만들 수 있는 로마 숫자의 최댓값을 정수 하나로 한 줄에 출력한다. 만들 수 있는 로마 숫자가 없으면 $0$을 출력한다.