Grid
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Given a n \times n grid, with each point having a value a_ {i, 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] if it satisfy one of the conditions. Otherwise, it's a bad point.

\bullet \ \ i \ = \ 1

\bullet   1 < i \le n , 1< j < n  and\ \ [i -1,\ j - 1] and [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 \sim n^2, 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, k(2 \leq n\leq 140,0 \le k \le 1).

The next n lines contains n space separated integers a _ {i,j}(0\le a_{i,j} \le 10^9) representing the values of each cell of the grid.

输出描述:

The output contains n^2 lines.

The i-th line represents the answer when m \ = \ i.
示例1

输入

复制 
2 0
2 3
4 5

输出

复制 
3
5
-1
-1
示例2

输入

复制 
4 0
2 1 0 8
0 10 1 0
0 0 0 0
0 0 0 0

输出

复制 
8
10
12
20
21
22
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1