Route 2#856
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 in the cells on the path of length (a cell can be visited several times).
The first line contains integers and k~(2 ≤ n ≤ 100, 1 ≤ k ≤ 2000), separated with a space. Each of the next rows contains numbers and describe the matrix. All numbers in matrix are integer and lie in the range from to .
Print one number - the maximum sum.
Example 1