• Встречи
  MEETINGS

Описание
После тяжелой трудовой недели программист решил отдохнуть и развлечься, посетив несколько ночных клубов. Ночные клубы города, где живёт программист, расположены в NxN центральных кварталах города по одному клубу на квартал (см.рис). К сожалению, задача осложняется тем, что в некоторых из клубов программист может встретить знакомых девушек, которые, естественно, будут ему мешать. 

Из предыдущего опыта программист знает, что если общаться с одной и той же девушкой более часа подряд, то начинает сильно болеть голова. Поэтому он решил, что будет каждый час в течение H часов, начиная с полуночи, переходить из клуба в клуб, соседний по горизонтали или вертикали.

Клуб  Клуб  Клуб
(1, 1)  (1,2)  (1,3)
Клуб  Клуб  Клуб
(2, 1)  (2,2)  (2,3)
Клуб  Клуб  Клуб
(3, 1)  (3, 2)  (3,3)
       
Программист заранее составил таблицу, каждый элемент которой G_i,j,h - среднее количество знакомых девушек, встречавшихся ему в предыдущие дни в клубе (i, j) в течение часа с номером h.

Задание
Требуется определить маршрут, при котором математическое ожидание числа встреченных за H часов знакомых девушек будет наименьшим. Математическое ожидание в данном случае равно сумме значений G_i,j,h, соответствующих клубам, включенным в маршрут, и времени их посещения.

Технические условия

Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничения: 1<=N<=90, 1<=H<=24;  0<=G_i,j,h<=100

Входной файл
В первой строке входного файла содержатся целые числа N и H. Далее расположены H матриц размером N строк по N чисел в каждой строке, содержащих вещественные числа - среднее количество девушек в каждом клубе в час номер 1, 2, …, H.

Выходной файл
Выходной файл должен содержать единственное вещественное число - минимальное математическое ожидание числа девушек точностью не менее трёх старших значащих цифр. (т.е. ответ должен совпадать с правильным по крайней мере в трёх старших разрядах).

Пример:

INPUT.TXT
2  2
1  1.5
3.1  0.4
0  4.1
0.9  3

OUTPUT.TXT
1.3