게으른 소

시간 제한1초메모리 제한128 MB

요약

맨해튼 거리 K 안에 든 풀의 합이 가장 큰 시작 칸을 골라 그 합을 구합니다.

난이도: 보통10점 중 5점
유형: 누적 합, 행렬
정답자: 아직 제출이 없습니다

문제

여름 더운 날, 소 Bessie는 꽤 게을러졌습니다. 들판에서 자신을 어디에 두면 짧은 거리 안에서 최대한 많은 맛있는 풀에 닿을 수 있을지 찾고 싶습니다.

Bessie가 사는 들판은 $N \times N$ 격자로 표현됩니다 ( $1 \le N \le 400$ ). $r$ 행 $c$ 열 ( $1 \le r,c \le N$ ) 칸에는 풀 $G(r,c)$ 단위가 있습니다 ( $0 \le G(r,c) \le 1000$ ). 시작 칸에서 Bessie는 최대 $K$ 걸음 ( $0 \le K \le 2N$ )만 걸을 의향이 있습니다. 한 걸음은 현재 칸에서 북, 남, 동, 서 중 하나로 인접한 칸으로 이동합니다.

시작 위치를 잘 고르면 $K$ 걸음 이내에 도달할 수 있는 풀의 양을 최대로 만들 수 있습니다. 그 최댓값을 구하세요.

입력

1번째 줄: 정수 $N$ , $K$ .
다음 $N$ 줄: $N$ 개의 정수로 $r$ 번째 줄의 격자 값.

출력

1번째 줄: 시작 위치를 최적으로 고를 때 $K$ 걸음 이내에 도달할 수 있는 풀의 최대 총량.

힌트

시작 칸을 바꿔가며 $K$ 걸음 이내에 도달 가능한 칸들의 풀 합을 계산하면 됩니다.

예제5

예제 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

예상 출력

예제 2
입력
```
1 0
137
```
예상 출력
```
137
```

예제 3

입력

3 1
978 883 970
869 57 93
86 369 855

예상 출력

예제 4

입력

4 3
243 606 557 133
378 937 618 485
640 594 67 620
13 930 857 480

예상 출력

예제 5

입력

6 2
241 310 105 738 405 490
158 92 68 20 411 562
939 296 819 783 60 227
532 549 368 283 798 176
846 108 268 219 965 949
26 848 656 826 266 819

예상 출력