Hide

IXth Problem

Emily recently learned about the Roman Empire and its civilization at school. One aspect that was especially fascinating to her is the number system that they used, the Roman numerals. The Roman number system uses seven distinct digits, each representing a different value and denoted by a letter, where I is $1$, V is $5$, X is $10$, L is $50$, C is $100$, D is $500$ and M is $1\, 000$. Multiples of $1$, $10$, $100$ and $1\, 000$ are then written according to the following table:

$\times $

1

2

3

4

5

6

7

8

9

$1$

I

II

III

IV

V

VI

VII

VIII

IX

$10$

X

XX

XXX

XL

L

LX

LXX

LXXX

XC

$100$

C

CC

CCC

CD

D

DC

DCC

DCCC

CM

$1\, 000$

M

MM

MMM

           

Most of the numerals in this table are formed additively, i.e. by summing the values of the digits. For example, LXX is $50+10+10=70$. Columns $4$ and $9$, however, use so-called subtractive notation, where IV is read as $5-1$, IX is read as $10-1$, and so on.

Each number from $1$ to $3\, 999$ is written as a combination of numerals from the table, using at most one numeral from each row and going from bottom to top. For instance, $2\, 021$ is MMXXI and $594$ is DXCIV. Note that in this number system it is not possible to write numbers greater than $3\, 999$ and also that subtractive notation can only be used in the six cases above (e.g. IC is not considered a valid Roman numeral).

Emily found a bunch of old Scrabble sets in her attic. She threw out all the tiles with letters other than the Roman digits and started forming Roman numerals from the remaining tiles. It is easy to form valid numerals from the tiles by using just one tile per numeral, but what is the minimal number of numerals that can be formed while still using all the available tiles?

Input

The input consists of:

  • One line with seven integers $m$, $d$, $c$, $\ell $, $x$, $v$ and $i$ ($0 \le m,d,c,\ell ,x,v,i \le 10^{18}$), which respectively are the number of M, D, C, L, X, V and I tiles that must be used.

There is at least one tile, that is $m+d+c+\ell +x+v+i \ge 1$.

Output

Output an integer $n$, the minimal possible number of Roman numerals that can be formed while using all of the tiles in the input. Then output an optimal solution in the following format.

  • An integer $k$, the number of distinct Roman numerals used in this solution.

  • $k$ pairs of a Roman numeral and a positive integer indicating how often this numeral is used in this solution.

The solution must consist of exactly $n$ numerals in total and must use exactly the specified number of each letter. The $k$ Roman numerals in the solution must be distinct. You do not need to minimize $k$. If there is more than one optimal solution, any one of them will be accepted.

Sample Input 1 Sample Output 1
4 1 7 1 3 1 3
2
2
MMDCCCLXX 1
MMCCCXCVIII 1
Sample Input 2 Sample Output 2
0 0 0 300 2000 1000 2100
1000
2
XXVIII 700
LXXV 300
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 4.5medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in