깡충깡충 사방치기

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

게임은 한 변의 크기가 $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$ 이하입니다.

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