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:

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?

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 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.