В Берляндии используют банкноты \(n\) различных типов. Банкноты \(i\)-го типа имеют номинал \(10^{a_i}\) бурлей (бурли — валюта, используемая в Берляндии); номинал банкнот первого типа равен \(1\).
Давайте обозначим \(f(s)\) как минимальное количество банкнот, необходимое для представления ровно \(s\) бурлей. Например, если номиналы банкнот, используемых в Берляндии, составляют \(1\), \(10\) и \(100\), то \(f(59) = 14\): \(9\) банкнот номиналом \(1\) и \(5\) банкнот номиналом \(10\) могут быть использованы для представления ровно \(9 \cdot 1 + 5 \cdot 10 = 59\) бурлей, и это невозможно сделать меньшим количеством банкнот.
Для заданного целого числа \(k\) найдите минимальное положительное число бурлей \(s\), которое не может быть представлено с помощью \(k\) или меньшего количества банкнот (то есть \(f(s) > k\)).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное положительное число бурлей \(s\), которое не может быть представлено с помощью \(k\) или меньшего количества банкнот.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 13
0 1 2
2 777
0 4
3 255
0 1 3
10 1000000000
0 1 2 3 4 5 6 7 8 9
|
59
778
148999
999999920999999999
|