Moving 2

Interview

Time limit2sMemory limit512 MB

Summary

Given an N by N grid of candy amounts, collect the most candy over K monotone paths from (1,1) to (N,N), counting each cell only once.

Level: Medium7 of 10
Topics: Dynamic programming, Implementation, Matrix
Solved: No attempts yet

Problem

Jungyu is trapped in a maze of size $N \times N$ . The maze is divided into rooms of size $1 \times 1$ , and every room holds some candy. A room is written $(r, c)$ , which means row $r$ and column $c$ . The top left room is $(1, 1)$ and the bottom right room is $(N, N)$ .

Jungyu starts at $(1, 1)$ and travels to $(N, N)$ a total of $K$ times. From $(r, c)$ he can move only to $(r+1, c)$ or $(r, c+1)$ , and he can never leave the maze. When he enters a room he takes every candy still in it. A room he has already emptied gives him nothing on a later visit. He may take the same route more than once.

Find the largest number of candies he can collect once the $K$ trips are done.

Input

The first line contains the maze size $N$ and the number of trips $K$ . ( $1 \le N \le 50$ , $0 \le K \le 10$ )

Each of the next $N$ lines contains $N$ numbers. The $c$ -th number on the $r$ -th line is the amount of candy in room $(r, c)$ , which is at least 0 and at most 1,000.

Output

Print on the first line the largest number of candies Jungyu can collect over the $K$ trips. If $K$ is 0 he makes no trip, so print 0.

Examples7

Example 1
Input
```
3 2
1 2 3
0 2 1
1 4 2
```
Expected output
```
15
```
Example 2
Input
```
1 0
7
```
Expected output
```
0
```
Example 3
Input
```
1 10
1000
```
Expected output
```
1000
```
Example 4
Input
```
3 0
5 5 5
5 5 5
5 5 5
```
Expected output
```
0
```
Example 5
Input
```
2 1
1 1000
1 1
```
Expected output
```
1002
```
Example 6
Input
```
2 2
1 2
3 4
```
Expected output
```
10
```
Example 7
Input
```
3 3
1 2 3
4 5 6
7 8 9
```
Expected output
```
45
```