题目描述

现在魔法科高校里发生了超能力外溢的事件。大家对怎么约束超能力束手无策。是你翻盘成为万众瞩目的焦点的时候了！

魔法科高校可以抽象为一个n行m列的网格图。一些点上有外溢的超能力数值，另一些点上有超能力抑制器。沿着超能力抑制器的指向方向发射，可以控制该方向上某一个网格内外溢的超能力并清零。

由于超能力控制器发出的控制光线非常强大，因此所有控制器形成的路线不能有交叉。

你的任务是最大化能够抑制的超能力数值的总和。

保证没有超能力抑制器直接打到另一个超能力抑制器。

输入格式

第一行两个正整数$N,M$

接下来$N$行，每行$M$个整数，0代表空地，-1、-2、-3、-4分别代表朝向为北/南/西/东的超能力抑制器，否则代表了该地外溢的超能力数值。

输出格式

一行一个整数，最多抑制的超能力数值。

4 5
0 0 -2 0 0
-4 0 5 4 0
0 -4 3 0 6
9 0 0 -1 0

12

数据规模与约定

对于$20\%$的数据，$1 \le N, M \le 5$

对于60%的数据，$1 \le N, M \le 20$

对于$100\%$的数据，$1 \le N, M \le 50$，每个网格中外溢的超能力数值不超过1000。

大样例

大样例下载