Max has found himself in Valentine's Land, a field represented as an ~N\times M~ grid with either cookies or boulders. Each cookie has a particular value ~V_i~ and Max starts on the top-left corner.

In one second, Max can either move directly up, down, left, or right as long as he stays on the grid and does not move into a boulder. Additionally, if he chooses to do so, he can pick up the cookie corresponding to the cell he is currently at and instantly teleport back to the top-left corner. However, if he picked up a cookie before, then this cookie must have a strictly higher value than the last.

Max can spend at most ~K~ seconds moving. What is the largest sum of cookies he can pick up?

Constraints

~1\le N, M~

~N\times M\le 10^3~

~0\le V_i\le 10^9~

~0\le K\le 10^4~

Input Specification

The first line contains three integers ~N~, ~M~, and ~K~.

The next ~N~ lines each contains ~M~ integers, which describes the ~N\times M~ grid. For each cell, if the value listed is nonnegative, then it is a cookie with the same value. Otherwise, it is a boulder. The top left corner will be a 0.

Output Specification

One integer, the maximum total value of cookies Max can get.

Sample Input

3 4 7
0 0 -1 8
1 0 -1 0
0 0 0 0

Sample Output

8

Sample Input

3 4 4
0 0 -1 8
1 0 -1 0
0 0 0 0

Sample Output

1