Палиндром

Дана строка, состоящая из строчных латинских букв. Требуется найти самый длинный палиндром, который можно получить, удалив не более М букв.

Палиндром — это строка ненулевой длины, которая читается одинаково слева направо и справа налево.

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

Первая строка содержит последовательность латинских букв (длина строки не превышает 1000 символов).

Вторая строка содержит число М (0 ≤ M ≤ 1000) — максимальное количество разрешённых удалений.

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

Выведите палиндром максимальной длины. Если таких палиндромов несколько, выведите первый в алфавитном порядке. Если палиндром создать невозможно, выведите -1.

Примеры