Паліндром

Лимит времени 1 секунда

Лимит использования памяти 64 MiB

Дано рядок, який складається з малих латинських літер. Потрібно знайти найдовший рядок-паліндром, який можна отримати викреслюванням деяких літер не більше М разів.

Паліндромом будемо вважати рядок ненульової довжини, який читається однаково зліва направо і справа наліво.

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

Перший рядок - послідовність з латинських літер (довжина рядка не перевищує 1000 літер).

Другий рядок - число М (0 ≤ M ≤ 1000) - максимальна кількість можливих викреслень.

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

Максимальний за довжиною паліндром.

Якщо таких декілька, то виведіть перший за алфавітним порядком.

Якщо паліндром утворити неможливо, то виведіть -1.

Пример

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

aabbcaa
1

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

aabbaa

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

aabbcaa
0

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

-1