Хомяку Арсению было слишком скучно на школьных уроках, поэтому он придумал для себя интересную задачу. Арсений хочет найти такое минимальное $$$n$$$-значное число $$$x$$$, чтобы существовало $$$k$$$ $$$n$$$-значных чисел, не превосходящих число $$$x$$$, с одинаковой суммой цифр. Помогите хомяку решить эту задачу.
$$$n$$$-значное число — это неотрицательное целое число, запись которого в десятичной системе счисления состоит ровно из $$$n$$$ цифр и не содержит ведущих нулей.
В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 10^{6}$$$).
Во второй строке дано одно целое число $$$k$$$ ($$$1 \le k \le 10^{18}$$$).
Выведите $$$x$$$. Если $$$x$$$ не существует, выведите «$$$-1$$$» (без кавычек).
Тесты к этой задаче состоят из девяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы, всех тестов необходимых для неё групп и тестов из условия.
| Группа | Баллы | Доп. ограничения | |
| 1 | 12 | $$$n \le 3$$$, $$$k \le 100$$$ | – |
| 2 | 15 | $$$n \le 9$$$, $$$k \le 10^9$$$ | 1 |
| 3 | 13 | $$$n \le 18$$$ | 1, 2 |
| 4 | 14 | $$$n \le 1000$$$ | 1, 2, 3 |
| 5 | 10 | $$$k \le 20$$$ | – |
| 6 | 14 | $$$k \le 10^6$$$ | 1, 5 |
| 7 | 7 | $$$k \le 10^9$$$ | 1, 2, 5, 6 |
| 8 | 15 | – | 1–7 |
318
271
11
0
В первом примере в качестве $$$18$$$-и трёхзначных чисел, не превосходящих число $$$271$$$, с одинаковой суммой цифр подходят следующие числа: 109, 118, 127, 136, 145, 154, 163, 172, 181, 190, 208, 217, 226, 235, 244, 253, 262, 271.
