Given a n×nn \times nn×n grid, with each point having a value ai,ja_ {i, j}ai,j(coordinate is from 1∼n1 \sim n1∼n).
Now you need to select mmm points, one of which is considered as a good point [i,j][i, j][i,j] if it satisfy one of the conditions. Otherwise, it's a bad point.
∙\bullet∙ i = 1\ \ i \ = \ 1i=1
∙\bullet∙1<i≤n,1<j<n1 < i \le n , 1< j < n1<i≤n,1<j<n and [i−1, j−1]\ \ [i -1,\ j - 1][i−1,j−1] and [i−1, j+1][i -1, \ j + 1][i−1,j+1] are both selected
A selection is legal if and only if the number of bad points is less than or equal to kkk.
For m=1∼n2m=1 \sim n^2m=1∼n2, print the maximum value of the sum of all the points selected.
If there is no solution, output −1-1−1.
输入格式
The first line contains two integers n,kn, kn,k(2≤n≤140,0≤k≤12 \leq n\leq 140,0 \le k \le 12≤n≤140,0≤k≤1).
The next nnn lines contains nnn space separated integers ai,ja _ {i,j}ai,j(0≤ai,j≤1090\le a_{i,j} \le 10^90≤ai,j≤109) representing the values of each cell of the grid.
输出格式
The output contains n2n^2n2 lines.
The iii-th line represents the answer when m = im \ = \ im=i.