깡충깡충 사방치기

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

요약

n x n 격자의 각 칸에 동전 더미가 있고, (0,0)에서 시작해 같은 행이나 열로 k칸 이내에 있으면서 더 많은 동전이 있는 칸으로만 이동할 때, 모을 수 있는 동전의 최댓값을 구한다.

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

문제

사방치기는 분필, 보도블록, 뜀뛰기, 그리고 무언가를 줍는 놀이입니다. 이 문제의 변형에서는 돈까지 등장합니다.

게임은 한 변의 크기가 $n$ 인 정사각형 격자에서 진행됩니다. 각 칸은 $(p, q)$ 로 나타내며 $0 \le p < n$ , $0 \le q < n$ 입니다. 각 칸에는 $0$ 개 이상 $100$ 개 이하의 동전이 쌓여 있습니다.

참가자는 칸 $(0, 0)$ 에서 시작합니다. 참가자는 지금 서 있는 칸의 동전을 모두 주운 뒤, 가로 또는 세로 방향으로 다른 칸으로 뜁니다. 목적지 칸은 참가자의 도약 능력인 $k$ 칸 이내여야 하며(즉 같은 행 또는 같은 열에 있으면서 거리가 $k$ 이하여야 하고), 지금 있는 칸보다 동전이 반드시 더 많아야 합니다.

참가자는 더 이상 이동할 수 없을 때까지 계속 뛰며 동전을 모읍니다. $n$ , $k$ , 그리고 각 칸의 동전 개수가 주어질 때, 참가자가 모을 수 있는 동전 개수의 최댓값을 구하세요.

입력

두 정수 $n$ 과 $k$ 가 주어집니다 ( $1 \le n \le 100$ , $1 \le k \le 100$ ).
이어서 $n$ 개의 줄이 주어지며, 각 줄에는 $n$ 개의 정수가 있습니다. 첫 줄은 $(0,0), (0,1), \ldots, (0,n-1)$ 의 동전 개수를, 다음 줄은 $(1,0), (1,1), \ldots, (1,n-1)$ 을 나열하고, 이런 식으로 계속됩니다. 각 값은 $0$ 이상 $100$ 이하입니다.

출력

참가자가 모을 수 있는 동전 개수의 최댓값을 정수 하나로 출력합니다.

예제4

예제 1
입력
```
3 1
1 2 5
10 11 6
12 12 7
```
예상 출력
```
37
```
예제 2
입력
```
1 1
42
```
예상 출력
```
42
```
예제 3
입력
```
2 100
5 5
5 5
```
예상 출력
```
5
```
예제 4
입력
```
2 1
0 1
2 3
```
예상 출력
```
5
```