Задача №637. Маршрут(2)
Дана матрица \(N\)x\(N\), заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной \(K\) (клетку можно посещать несколько раз).
Входные данные
В первой строке находятся разделенные пробелом числа \(N\) и \(K\). Затем идут \(N\) строк по \(N\) чисел в каждой. 2 <= \(N\) <= 100, элементы матрицы имеют значения от 1 до 9999, 1 <= \(K\) <= 2000, все числа целые.
Выходные данные
Вывести одно число - максимальную сумму.
Примеры
Входные данные
5 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 100
Выходные данные
7
Сдать: для сдачи задач необходимо войти в систему