D. Минимальный путь
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана матрица размера $$$n \times n$$$, заполненная строчными латинскими буквами. Вы можете изменить не более $$$k$$$ букв в этой матрице.

Рассмотрим все пути из верхней левой клетки в правую нижнюю, в которых каждая следующая клетка является соседней справа или снизу с предыдущей. Каждому пути соответствует строка, которая получается выписыванием подряд букв во всех клетках, через которые проходит этот путь. Таким образом длина каждого пути равна $$$2n - 1$$$.

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

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если первая различная в $$$a$$$ и $$$b$$$ буква меньше в строке $$$a$$$.

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

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2000$$$, $$$0 \le k \le n^2$$$) — размер матрицы и число букв, которые вы можете изменить.

Каждая из следующих $$$n$$$ строк содержит строку из $$$n$$$ строчных латинских букв и описывает одну строку матрицы.

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

Выведите лексикографически минимальную строку, которая может соответствовать какому-то пути после того, как вы измените не более чем $$$k$$$ букв в матрице.

Примеры
Входные данные
4 2
abcd
bcde
bcad
bcde
Выходные данные
aaabcde
Входные данные
5 3
bwwwz
hrhdh
sepsp
sqfaf
ajbvw
Выходные данные
aaaepfafw
Входные данные
7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz
Выходные данные
aaaaaaadudsnz
Примечание

В первом примере можно изменить буквы «b» в клетках $$$(2, 1)$$$ и $$$(3, 1)$$$ на «a», тогда лексикографически минимальный путь проходит через клетки $$$(1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)$$$. Первая координата описывает номер строки, вторая — номер столбца.