U446447 分龟

今天邱邱人在野外抓了一只龟，由于它太肥了，所以邱邱人抓不起来。于是只能请你来帮助吃掉它了！

给出这只龟的构造 $m^2$ 个部位，你可以把这只龟选择性吃掉，其中每个部位都有一个美味值，但是你吃掉一个部位，这个部位四周的部位的美味值都会减少吃掉部位的美味值的一半。换个说法，若吃掉部位的美味值为 $a_i$，四周某个部位美味值为 $a_j$，吃掉 $i$ 后 $a_j\gets a_j-\lfloor a_i/2 \rfloor$。 你最多只能吃掉 $n$ 个部位，不要太贪心哦！ 你想让吃掉的美味值尽可能大。

第一行两个整数 $m,n$。 接下来 $m$ 行第 $i$ 行 $m$ 个整数 $a_{i,j}$ 表示第 $i$ 行第 $j$ 个部位的美味值。

输出最大美味值。

$1\le m\le 1000,0\le n\le 10^7,0\le \lvert a_i\rvert\le 10^9$ 对于四周的定义：$(i,j)$ 的四周是 $(i-1,j),(i+1,j),(i,j-1),(i,j+1)$，如若越界自行判断。 样例 2 解释：一种满足答案最大的选择顺序：$(2,2),(1,2),(1,1)$，答案为 $7$。可以证明答案不超过 $7$。