C. Задача Арсения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хомяку Арсению было слишком скучно на школьных уроках, поэтому он придумал для себя интересную задачу. Арсений хочет найти такое минимальное $$$n$$$-значное число $$$x$$$, чтобы существовало $$$k$$$ $$$n$$$-значных чисел, не превосходящих число $$$x$$$, с одинаковой суммой цифр. Помогите хомяку решить эту задачу.

$$$n$$$-значное число — это неотрицательное целое число, запись которого в десятичной системе счисления состоит ровно из $$$n$$$ цифр и не содержит ведущих нулей.

Входные данные

В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 10^{6}$$$).

Во второй строке дано одно целое число $$$k$$$ ($$$1 \le k \le 10^{18}$$$).

Выходные данные

Выведите $$$x$$$. Если $$$x$$$ не существует, выведите «$$$-1$$$» (без кавычек).

Система оценки

Тесты к этой задаче состоят из девяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы, всех тестов необходимых для неё групп и тестов из условия.

ГруппаБаллыДоп. ограничения
112$$$n \le 3$$$, $$$k \le 100$$$–
215$$$n \le 9$$$, $$$k \le 10^9$$$1
313$$$n \le 18$$$1, 2
414$$$n \le 1000$$$1, 2, 3
510$$$k \le 20$$$–
614$$$k \le 10^6$$$1, 5
77$$$k \le 10^9$$$1, 2, 5, 6
815–1–7
Примеры
Входные данные
3
18
Выходные данные
271
Входные данные
1
1
Выходные данные
0
Примечание

В первом примере в качестве $$$18$$$-и трёхзначных чисел, не превосходящих число $$$271$$$, с одинаковой суммой цифр подходят следующие числа: 109, 118, 127, 136, 145, 154, 163, 172, 181, 190, 208, 217, 226, 235, 244, 253, 262, 271.