eolymp
bolt
Try our new interface for solving problems
Problems

Route 2

Route 2

Time limit 1 second
Memory limit 128 MiB

Given a matrix n × n, filled with positive integers. The path starts in the upper left corner of the matrix. In one move you can go into the next vertical or horizontal cell (if it exists). You can not walk diagonally, you can not stay in one place. Find the maximum sum of numbers, standing in the cells on the path of length k (a cell can be visited several times).

Input data

In the first row the integers n and k (2n100, 1k2000), separated with a space, are given. Each of the next n rows contains n numbers and describe the matrix. All numbers in matrix are integer and lie in the range from 1 to 9999.

Output data

Print one number - the maximum sum.

Examples

Input example #1
5 7
1 1 1 1 1
1 1 3 1 9
1 1 6 1 1
1 1 3 1 1
1 1 1 1 1
Output example #1
21