Hippity Hopscotch

Time limit1sMemory limit128 MB

Summary

On an n by n grid of penny stacks, starting at (0,0) and jumping up to k cells in a row or column to a strictly larger stack, find the maximum total collected.

Level: Medium5 of 10
Topics: Dynamic programming, Sorting, Matrix
Solved: No attempts yet

Problem

The game of hopscotch involves chalk, sidewalks, jumping, and picking things up. In our variant, money is involved as well.

The game is played on a square grid of dimension $n$ : each grid location is labelled $(p, q)$ where $0 \le p < n$ and $0 \le q < n$ . On each grid location there is a stack of between $0$ and $100$ pennies.

A contestant begins by standing at location $(0, 0)$ . The contestant collects the pennies on the square where they stand, then jumps either horizontally or vertically to another square. The destination square must be within the contestant's jumping capability of $k$ locations (that is, it lies in the same row or the same column and is at most $k$ steps away), and it must hold strictly more pennies than the square the contestant is currently on.

The contestant keeps jumping and collecting until no legal move remains. Given $n$ , $k$ , and the number of pennies on each grid location, compute the maximum number of pennies the contestant can collect.

Input

A line with two integers $n$ and $k$ ( $1 \le n \le 100$ , $1 \le k \le 100$ ).
Then $n$ lines follow, each with $n$ integers. The first line lists the pennies at locations $(0,0), (0,1), \ldots, (0,n-1)$ ; the next line lists $(1,0), (1,1), \ldots, (1,n-1)$ ; and so on. Each value is between $0$ and $100$ .

Output

A single integer: the maximum number of pennies the contestant can collect.

Examples4

Example 1
Input
```
3 1
1 2 5
10 11 6
12 12 7
```
Expected output
```
37
```
Example 2
Input
```
1 1
42
```
Expected output
```
42
```
Example 3
Input
```
2 100
5 5
5 5
```
Expected output
```
5
```
Example 4
Input
```
2 1
0 1
2 3
```
Expected output
```
5
```