grid

题目描述

给出一张 $n \times n$ 的网格，每个点有权值 $a_{i,j}$ (坐标下标从 $1\sim n$ )

现在你需要选取$m$个点出来，一个选出的点被认为是好点当且仅当 $i=1$ $or$ $(i-1,j-1)$ 和 $(i-1,j+1) \ (1 <j <n)$ 这两个点都被选了 (若这两个点其中之一不在网格上，那么不符合条件），否则是一个坏点

一种合法的选点方案当且仅当坏点个数小于等于$k$

求对于 $m=1 \sim n^2$ ，选出的点权值和最大分别是多少

若不存在合法方案，输出 $-1$

输入格式

第一行两个整数 $n,k$

接下来 $n$ 行每行 $n$ 个整数，第 $i$ 行第 $j$ 个数代表 $a_{i,j}$

输出格式

输出 $n^2$ 行第 $i$ 行代表 $m=i$ 时的答案。

样例

样例输入 #1

2 0
2 3
4 5

样例输出 #1

3
5
-1
-1

样例输入 #2

2 1
2 3
4 5

样例输出 #2

5
8
10
-1

样例输入 #3

4 0
2 1 0 8 
0 10 1 0
0 0 0 0
0 0 0 0

样例输出 #3

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

样例输入 #4

5 1
5 0 5 0 0 
0 140 0 10 0
0 0 150 0 0
0 0 0 0 0
0 0 0 0 0

样例输出 #4

150
155
160
300
310
310
310
310
310
310
310
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

数据范围与限制

对于所有数据，保证

$2\leq n\leq 140, \ k\leq 1, \ 0\le a_{i,j} \le 10^9$

任务编号	任务分数	特殊限制
$1$	$10$	$n\le 4, \ k=0$
$2$	$20$	$n\le 9, \ k=0$
$3$		$k=0$
$4$	$30$	$n\le 50$
$5$	$20$	无特殊限制

注意本题采用捆绑测试