9073: Grid

Given a $n\times n$ grid, with each point having a value ai,ja_ {i, j}ai,j(coordinate is from $1\sim n$).

Now you need to select $m$ 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$

$\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 $k$.

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$.

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 $n$ lines contains $n$ 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 $i$-th line represents the answer when $m=i$.