Hide

Problem C
Cheaper Drink

Instead of worrying about the current hyperinflation you decide to go down to the local bar and have a drink.

The prices at the bar are displayed using magnetic signs with numbers printed on them, with each magnet showing one or more digits. For instance, the price of $1106$ megacredits is displayed like this:

\includegraphics[width = .2\textwidth ]{img/from.png}

While the bartender is busy serving the next customer, you have just enough time to rearrange the price of your favourite beverage to make it as cheap as possible. But be quick about it!

Invidual magnets can be moved around in any order and turned upside-down. The numbers are shown in a script that makes it difficult for the bartender to distinguish $0$, $1$, and $8$ from their upside-down counterpart. Moreover, $6$ and $9$ look the same when one is turned upside-down. The example price above could be made almost ten times cheaper by turning the first magnet:

\includegraphics[width = .2\textwidth ]{img/to.png}

You have to use all the magnets, otherwise the bartender will immediately suspect foul play.

Input

On the first line, the number $n$ of magnets, with $1\in \{ 1,\ldots , 1\, 000\} $. On each of the following $n$ lines, exactly one sequence $m_ i$ of digits describing the $i$th magnet. Each magnet $m_ i$ for $i\in \{ 1,\ldots , n\} $ consists of at least one and at most $10$ digits from $0$, $1$, $\ldots $, $9$. The price currently displayed on the bar is the integer described by the juxtaposition $m_1\cdots m_ n$ of the magnets in the order they are given, from left to right. Note that a magnet can be all $0$s, even though the current price at the bar, alas!, is certainly not.

Output

A single line containing the cheapest price formed by the magnets $m_1,\ldots ,m_ n$, rearranged in any order, and each of them possibly turned upside-down.

Sample Input 1 Sample Output 1
2
110
6
0116
Sample Input 2 Sample Output 2
2
7
72
727

Please log in to submit a solution to this problem

Log in