Arithmetic and Dice

Time limit2sMemory limit1024 MB

Summary

Given n dice with digits 0 to 9 on their faces, find the smallest natural number that cannot be built, where dice are reusable across numbers.

Level: Medium6 of 10
Topics: Graph, Greedy, Math
Solved: No attempts yet

Statement

Aurora has $n$ dice. Each die has six faces, and each face shows a digit from $0$ to $9$ . The digits on one die may repeat.

The fairies decided to teach Aurora arithmetic by giving her a task: build numbers from the dice. Aurora may pick any set of dice, turn each chosen die to any face, and arrange the dice in any order to form the desired number. Aurora never builds a number with leading zeros.

To help Aurora practice, the fairies want her to build the natural numbers one by one in increasing order. The dice used to build one number can be used again for the next numbers. Help the fairies find the smallest natural number that Aurora cannot build with the given dice.

Input

The first line contains an integer $n$ , the number of dice ( $1 \le n \le 100\,000$ ).

Each of the next $n$ lines contains a string of six digits $a_{i,1}, a_{i,2}, \ldots, a_{i,6}$ ( $0 \le a_{i,j} \le 9$ ), the digits on the faces of die $i$ .

Output

Print the smallest natural number that Aurora cannot build.

Examples3

Example 1
Input
```
2
012345
098765
```
Expected output
```
11
```
Example 2
Input
```
3
123456
789012
345678
```
Expected output
```
90
```
Example 3
Input
```
5
111111
222222
333333
444444
555555
```
Expected output
```
6
```