만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

산술과 주사위

시간 제한2초메모리 제한1024 MB

요약
주사위 각 면에 적힌 숫자로 만들 수 없는 가장 작은 자연수를 구하며, 주사위는 다음 수를 만들 때 다시 쓸 수 있습니다.
난이도

보통10점 중 6점

유형
그래프, 그리디, 수학
정답자
아직 제출이 없습니다

문제

아우로라에게는 주사위 nn개가 있습니다. 각 주사위에는 여섯 개의 면이 있고, 각 면에는 00부터 99까지의 숫자가 하나씩 적혀 있습니다. 한 주사위에 같은 숫자가 여러 번 적혀 있을 수 있습니다.

요정들은 아우로라에게 산술을 가르치려고 주사위로 수를 만드는 과제를 내기로 했습니다. 아우로라는 주사위를 원하는 만큼 골라, 각 주사위의 원하는 면이 위로 오도록 돌리고, 원하는 수가 되도록 임의의 순서로 늘어놓을 수 있습니다. 아우로라는 앞자리가 0인 수는 만들지 않습니다.

아우로라가 연습할 수 있도록, 요정들은 자연수를 작은 수부터 차례로 만들라고 시키려 합니다. 어떤 수를 만드는 데 쓴 주사위는 다음 수를 만들 때 다시 쓸 수 있습니다. 주어진 주사위로 아우로라가 만들 수 없는 가장 작은 자연수를 구해 주세요.

입력

첫 번째 줄에 주사위의 개수 nn이 주어집니다 (1≤n≤100 0001 \le n \le 100\,000).

이어지는 nn개의 줄에는 각각 주사위 ii의 여섯 면에 적힌 숫자 ai,1,ai,2,…,ai,6a_{i,1}, a_{i,2}, \ldots, a_{i,6}이 여섯 자리 문자열로 주어집니다 (0≤ai,j≤90 \le a_{i,j} \le 9).

출력

아우로라가 만들 수 없는 가장 작은 자연수를 출력합니다.

예제3

  1. 예제 1

    입력
    2
    012345
    098765
    
    예상 출력
    11
    
  2. 예제 2

    입력
    3
    123456
    789012
    345678
    
    예상 출력
    90
    
  3. 예제 3

    입력
    5
    111111
    222222
    333333
    444444
    555555
    
    예상 출력
    6