Обучение - Головоломная лотерея

Задача B. Головоломная лотерея ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	A. Klenin	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	128 Мб
Выходной файл:	output.txt

Условие

Журнал кроссвордов опубликовал новую головоломку. Она представляет собой квадрат размером $N \times N$ , в каждую клетку которого вписана малая латинская буква. Последовательности букв, которые можно построить, начиная с некоторой клетки и перемещаясь на соседние по горизонтали и вертикали, назовём словами. При построении слова запрещено дважды посещать одну и ту же клетку.

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

Формат входного файла

Первая строка содержит числа

$N\,L$ , далее идут

$N$ строк по

$N$ символов в каждой.

Формат выходного файла

Файл должен содержать единственную строку из

$L$ символов — наиболее часто встречающееся слово.

Ограничения

$1 \le N \le 35, 1 \le L \le 8,\,L \le N^2$

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`2 2 ba ac`	`ab`
2	`5 3 adfaf cadda bbeae edecb fdecc`	`ada`