F. Pseudo-Roman Number @ USU Junior Contest October'2003 @ Timus Online Judge

F. Pseudo-Roman Number

Time limit: 1.0 second
Memory limit: 64 MB

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: A₁A₂…A_n, 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 A₁A₂…A_n the following two statements are correct:

[A_i] ≥ [A_i+1] or
([A_i] < [A_i+1] ≤ 10[A_i] and [A_i] = 10^k), where i < n.

Before a numeral there may not be more than one lower numeral.
[A_i] ≥ [A_i+1] ≥ [A_i+2], or [A_i+2] < [A_i] < [A_i+1], or [A_i+1] < [A_i+2] ≤ [A_i], where i < n − 1
A₁ = [A₁].
A₁A₂…A_n = A₂…A_n − [A₁], if [A₁] < [A₂].
A₁A₂…A_n = A₂…A_n + [A₁], if [A₁] > [A₂].

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.

Input

There is a decimal integer number N, 1 ≤ N ≤ 10²⁰⁰³.

Output

Output the integer K — that is an amount of numerals in pseudo-roman notation of the number N.

Sample

input	output
1939	8

Notes

1939 = MCMXXXIX

Problem Author: Alexander Ipatov
Problem Source: Open collegiate programming contest for high school children of the Sverdlovsk region, October 11, 2003