题目背景

骷髅洞穴是星露谷物语 $(Stardew$ $Valley)$ 位于沙漠地图深处的一个无限层级洞穴，是游戏后期最具挑战性也回报最丰厚的区域之一，这里的矿物数量与价值会随着层数的增加而增加。青藤现在正位于第 $114514$ 层，他只剩下一个樱桃炸弹且体力所剩无几，你能帮他找到最佳的炸弹放置位置来得到最大价值吗?

题目描述

给定一个 $n \times m$ 的二维网格，表示当前矿洞的地图。网格中的元素含义如下：

• -1 表示地图边界（不可通行不可放置）
• 0 表示空地
• 1 表示普通石头
• 大于 1 的整数表示价值不同的矿石

爆炸覆盖范围:以炸弹格为原点，所有曼哈顿距离$≤ 4$ 的格子会受到影响，但与炸弹在同一行或同一列且距离为 $4$ 的那四个格子不受影响(具体查看样例解释)。

请找到一个最佳的炸弹放置位置，使得爆炸范围内矿石(不计算石头价值)的总价值最大化。

注意：炸弹可以放置在任意非边界位置（即值不为-1的位置），青藤会尽力清除放置位置的障碍物。

输入格式

每个测试文件仅有一组测试数据。

第一行包含两个整数 $n$ 和 $m$ $(10\leqslant n,\ m\leqslant1000)$，表示网格的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示矿洞网格。整数之间用空格分隔。

任何矿石价值不超过$50000$。

输出格式

输出一行一个整数，表示最大收益。

10 11
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1 1 4 3 8 2 5 1 5 7 -1 
-1 9 5 9 6 2 9 -1 -1 8 -1 
-1 1 9 5 2 9 9 -1 -1 3 -1 
-1 8 5 1 8 7 4 9 5 4 -1 
-1 6 3 4 3 4 3 8 9 7 -1 
-1 7 2 -1 -1 7 4 6 6 7 -1 
-1 8 9 -1 -1 1 1 6 5 3 -1 
-1 5 9 2 6 6 7 9 9 3 -1 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

172

样例解释

爆炸范围如图所示: