NTNU 23. mars 2002


Problem E - Tull med romertall

Du har valgt latin som studieretningsfag. Læreren drømmer seg ofte tilbake til det gamle Rom, han liker ikke det arabiske titallssystemet engang. For ham er det en forutsetning at elevene kan regne med romertall. Derfor har han gitt alle elevene 20 matteoppgaver, hvorav alle går ut på å legge sammen to tall. Du ser at dette kommer til å bli tidkrevende, og det vil ikke overraske deg om du får samme oppgave igjen om noen dager. Derfor bestemmer du deg for å skrive et program til å gjøre jobben.

For å unngå misforståelser, definerer vi romertallene på følgende måte: Et romertall består av en eller flere av bokstavene I,V,X,L,C,D og M. Disse har følgende verdier:

I 1
V 5
X 10
L 50
C 100
D 500
M 1000
Romertallene konstrueres ved å sette sammen bokstavene, og de kan enten brukes til å legge sammen, eller trekke i fra. Hvis to bokstaver på rad har samme verdi, eller bokstav 2 har lavere verdi, oppfattes det som at de legges sammen.

CV = 105
XXX = 30
Hvis en bokstav med lavere verdi enn den neste optrer, skal dette forstås som at verdien av den første bokstaven skal trekkes fra den andre.

Eksempler:

IV = 4
XC = 90
De hele tallene konstrueres så ved å kombinere disse to teknikkene. Eksempler på romertall:
XVII = 17
MDCCCLIX = 1859
En bokstav kan aldri gjentas mer enn tre ganger når den brukes til å legge til summen (unntaket er M, som kan gjentas i begynnelsen av et tall ubegrenset antall ganger). En bokstav kan aldri gjentas mer enn en gang når den brukes til å trekke fra.

Når en bokstav er brukt til å trekke i fra, kan de neste bokstavene ikke ha en høyere verdi (rent bortsett fra den neste bokstaven, som naturligvis må ha en høyere verdi).

Dette betyr at vi kan skrive MXMIII for 1993 eller CCXCIV for 294. Mens vi ikke kan skrive ILV for 54 eller LIL for 99. Legg merke til at noen tall vil kunne skrives på flere måter, for eksempel kan 299 skrives CCXCIX eller CCIC.

Oppgaven går ut på addere to romertall, og gi svaret som et romertall. Hver input-linje inneholder to romertall, separert av mellomrom. Ouput skal være et enkelt romertall, på en linje.

Input

To romertall på en linje, separert med mellomrom.

Output

Summen av de to romertallene, skrevet (som romertall) på en linje.

Ingen av tallene som skal legges sammen er større enn 2500 (heltallsverdi).

Eksempel

Input:

MXVI XIV

Output:

MXXX