Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Поле, на котором живёт Беси, описывается решёткой N*N квадратных ячеек (1 <= N <= 400). Ячейка в строке r и колонке c (1 <= r,c <= N) содержит G(i,j) единиц травы (0 <= G(i,j) <= 1000). От своей начальной ячейки Беси хочет сделать не более K шагов (0 <= K <= 2*N). Каждый шаг – это переход в соседнюю ячейку (на север, юг, запад или восток от текущей).
Например, предположим задана такая решётка где B описывает начальную позицию Беси (строка 3, колонка 3)
50 5 25* 6 17 14 3* 2* 7* 21 99* 10* 1*(B) 2* 80* 8 7* 5* 23* 11 10 0 78* 1 9
Если K=2, то для Беси достижимы только ячейки, помеченные *.
Пожалуйста, помогите Беси определить максимальное количество травы, которое она может достичь, если выберет оптимальное положение на решётке.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Целые числа N и K.
* Строки 2..1+N: Строка r+1 содержит N целых чисел, описывающих строку r решётки.
Формат выходных данных
Примечание
В примере выше Беси может достичь 342 единицы травы, если разместится в середине решётки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9
|
342
|