D. Путешествие
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Миша живет в стране, в которой есть $$$n$$$ городов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Он живет в городе $$$1$$$.

Между каждой парой городов ходит поезд. Назовем маршрутом проезд по поезду из города $$$i$$$ в город $$$j$$$, где $$$i \neq j$$$. В частности, всего есть $$$n(n-1)$$$ разных маршрутов. У каждого маршрута есть своя стоимость, и стоимость маршрута из города $$$i$$$ в город $$$j$$$ может отличаться от стоимости маршрута из города $$$j$$$ в город $$$i$$$.

Миша хочет начать в городе $$$1$$$, совершить ровно $$$k$$$ переездов из одного города в другой, и в конце снова оказаться в городе $$$1$$$. Миша — любитель экономить, так что он хочет, чтобы его путешествие было как можно более дешевым. Обратите внимание, что Миша может посещать один город и даже проезжать по одному маршруту несколько раз.

Миша считает, что путешествие удалось, если среди маршрутов, которые он использовал в своем путешествии, нельзя найти нечетный цикл. Иначе говоря, если можно начать в каком-то городе $$$v$$$, который посетил Миша, проехать по нечетному числу маршрутов, которые использовал Миша, вернувшись в город $$$v$$$, то путешествие считается неудачным.

Ваша задача помочь Мише, и найти самое дешевое (с минимальной суммой стоимостей маршрутов на нем) путешествие, которое Миша будет считать удачным.

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

В первой строке записано два целых числа $$$n,k$$$ ($$$2 \leq n \leq 80; 2 \leq k \leq 10$$$): количество городов в стране и требуемое количество маршрутов в путешествии Миши. Гарантируется, что $$$k$$$ четное.

В следующих $$$n$$$ строках записано описание стоимостей маршрутов, $$$j$$$-е число в $$$i$$$-й строке равно стоимости маршрута из города $$$i$$$ в город $$$j$$$, если $$$i \neq j$$$, иначе число равно нулю (маршрутов $$$i \to i$$$ нет). Все стоимости маршрутов — целые числа от $$$0$$$ до $$$10^8$$$.

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

Выведите одно целое число: минимальная сумма стоимостей маршрутов в удачном путешествии.

Примеры
Входные данные
5 8
0 1 2 2 0
0 0 1 1 2
0 1 0 0 0
2 1 1 0 0
2 0 1 2 0
Выходные данные
2
Входные данные
3 2
0 1 1
2 0 1
2 2 0
Выходные данные
3