На день рождения маленькой Маше-растеряше подарили набор кубиков, о которых она давно мечтала. Набор состоит из n кубиков.
На каждой из 6 граней каждого кубика написана ровно одна цифра от 0 до 9. Маше стало интересно для какого наибольшего натурального числа x она может составить все числа от 1 до x при помощи кубиков.
Для этого Маша может поворачивать кубики и ставить их в ряд. После этого она смотрит на верхние грани использованных кубиков слева направо и составляет из этих цифр число.
Число не может содержать лидирующие нули. При составлении числа не обязательно использовать все кубики. Если Маша не может получить даже число 1, то следует вывести число 0.
Обратите внимание: Маша не может получить цифру 6 из цифры 9, или 9 из 6 при перевороте кубика.
Выходные данные
Выведите единственное число — такое максимальное x, что Маша-растеряша может собрать из кубиков все числа от 1 до x или 0, если она не может собрать даже число 1.
Примечание
В первом примере Маша может составить все числа от 1 до 87, но число 88 она не может составить, так как нет двух кубиков с цифрами 8.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 1 2 3 4 5
6 7 8 9 0 1
2 3 4 5 6 7
|
87
|
|
2
|
3
0 1 3 5 6 8
1 2 4 5 7 8
2 3 4 6 7 9
|
98
|