IXth Problem

Emily recently learned about the Roman Empire and its civilization at school. One aspect she found especially interesting is the number system the Romans used, Roman numerals. The Roman numeral system uses seven distinct symbols, each with a different value and written as a letter: I is $1$, V is $5$, X is $10$, L is $50$, C is $100$, D is $500$, and M is $1000$. Multiples of $1$, $10$, $100$, and $1000$ are written according to the following table:

Most entries in this table are formed additively, that is, by summing the values of the symbols. For example, LXX is $50+10+10=70$. The columns for 4 and 9, however, use subtractive notation: IV is read as $5-1$, IX is read as $10-1$, and so on.

Every number from $1$ to $3999$ is written as a combination of entries from the table, using at most one entry from each row and going from bottom to top. For example, $2021$ is MMXXI and $594$ is DXCIV. Note that this number system cannot write numbers greater than $3999$, and subtractive notation is allowed only in the six cases above. For example, IC is not considered a valid Roman numeral.

Emily found a bunch of old Scrabble sets in her attic. She threw out all tiles with letters other than the Roman digits and started forming Roman numerals from the remaining tiles. It is easy to form valid numerals by using just one tile per Roman 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,i$ ($0 \le m,d,c,\ell,x,v,i \le 10^{18}$), which are the numbers 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 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 many times 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 is accepted.