Maximum Sum of Rhombic Area

The rhombus region of radius r is the set of cells whose Manhattan distance to the center plus one does not exceed r, that is, |row difference|+|column difference|<r. Considering only centers whose entire rhombus lies inside the matrix, find the maximum of these region sums.

输入格式

The first line contains rows cols radius; then rows lines of the matrix follow. Ranges added by this site: 1≤rows,cols≤200, 1≤radius≤200, |cell|≤10^6. If no complete rhombus exists, output 0.

输出格式

Output the maximum region sum; when the radius is so large that no complete region exists, output 0.

样例 1

输入：

6 6 3
0 2 4 1 6 4
5 1 3 4 1 5
0 1 2 1 2 1
1 3 2 1 1 2
4 1 3 6 5 5
6 7 5 3 1 2

输出：

35

样例 2

输入：

1 1 1
5

输出：

5

样例 3

输入：

2 2 3
1 2
3 4

输出：

0