We can’t say that all the programmers are absent-minded people but it is usual to some of them… Once Artemy Sidorovich tested his program. Particularly it was to be able to define a day of the week by the date. Artemy Sidorovich inputted "October 11, 2003" and got the answer "Saturday". "Aha!" — thought Artmy Sidorovich and started to search for a mistake (the calendar that was hung in his room said that October 11th, 2003 is Monday).
After an hour Artemy Sidorovich glances up and saw big digits in the calendar: 1999. Swearing under his breath and promising to through away the old calendar he looked at the clock. The hour hand was at the mark IIII. The day was almost finished.
— It’s interesting, — thought Artermy Sidorovich, — I’ve seen many times that the number 4 is written down by the Roman numerals as IV. It turns out that a decimal number can’t be represented by the Roman number unambiguously. He looked again at the calendar and thought so:
— Let the numbers 1, 5, 10, 50, 100, 500, 1000 be denoted by the Roman numerals I, V, X, L, C, D, M. Then the number 1999 may be represented as MDCCCCLXXXXVIIII or simply MIM. Or may be MCMXCIX. It’s evident that the record MIM is the shortest. But which one is correct?
In order to adjust differences Artemy Sidorovich decided:
We'll call a pseoudo-roman number the sequence of numerals: A1A2…An, where:
- Every numeral denotes on of the numbers 1, 5, 10, 50, 100, 500, 1000, … The different digits correspond to the different numbers. Let’s denote the number according to the numeral A as [A].
- There may be not more than 3 identical numerals one after another, if the numerals denote a power of 10 and not more than 2 identical numerals otherwise.
- In the number A1A2…An the following two statements are correct:
Before a numeral there may not be more than one lower numeral.
[Ai] ≥ [Ai+1] ≥ [Ai+2], or [Ai+2] < [Ai] < [Ai+1], or [Ai+1] < [Ai+2] ≤ [Ai], where i < n − 1
A1 = [A1].
- [Ai] ≥ [Ai+1] or
- ([Ai] < [Ai+1] ≤ 10[Ai] and [Ai] = 10k), where i < n.
A1A2…An = A2…An − [A1], if [A1] < [A2].
A1A2…An = A2…An + [A1], if [A1] > [A2].
Then the number 4 will be written down as IV, and not as IIII (according to the rule 2). The number 1999 will be written down as MCMXCIX. It’s not the shortest way but every number is represented unambiguously.
There is a decimal integer number N, 1 ≤ N ≤ 102003.
Output the integer K — that is an amount of numerals in pseudo-roman notation of the number N.
Problem Author: Alexander Ipatov
Problem Source: Open collegiate programming contest for high school children of the Sverdlovsk region, October 11, 2003