J. Наименьшее кратное

Дано число $X$ и набор цифр $D$. Допишите к $X$ справа наименьшее количество цифр из $D$ так, чтобы получившееся число делилось на $k$. Среди таких чисел выведите наименьшее.

Само число может быть чудовищно длинным, и перебирать его нельзя. Зато состояние — это остаток по модулю $k$, а их всего $k$. Приписывание цифры $d$ переводит остаток $r$ в $(10r + d) \bmod k$; получается граф на $k$ вершинах, и нужен кратчайший путь из остатка $X$ в ноль.

Чтобы среди кратчайших получилось наименьшее число, цифры на каждом шаге перебираются по возрастанию.

Первая строка содержит число $X$ (до 1000 цифр, без ведущих нулей) и число $k$ ($2 \le k \le 10^5$).

Вторая строка содержит количество цифр в наборе, третья — сами цифры через пробел.

Наименьшее подходящее число или $-1$, если его не существует.