题目

题目描述

Nick最近在玩一款很好玩的游戏，游戏规则是这样的：

有一个$n\times m$的地图，地图上的每一个位置要么是空地，要么是炮塔，要么是一些BETA狗，Nick需要操纵炮塔攻击BETA狗们。

攻击方法是：对于每个炮塔，游戏系统已经给出它可以瞄准的方向(上下左右其中一个)，Nick需要选择它的攻击位置，每一个炮塔只能够攻击一个位置，炮塔只能够向着它的瞄准方向上的某个位置发动攻击，当然炮塔也可以不进行攻击。炮塔威力强大，它可以且仅可以消灭目标位置上所有的BETA狗。

出于安全考虑，游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔，即对于任意一个炮塔，它所有可能的攻击位置上不存在另外一个炮塔。而且，如果把炮塔的起点和终点称为炮弹的运行轨迹，那么系统不允许两条轨迹相交(包括起点和终点)。

现在，选定目标位置以后，每一个炮塔同时开炮，你要告诉Nick，他最多可以干掉多少BETA狗。

输入格式

第一行两个正整数$n,m$，表示地图的规模。

接下来$n$行，每行$m$个整数，$0$表示空地，$-1$,$-2$,$-3$,$-4$分别表示瞄准上下左右的炮塔，若为正整数$p$，则表示该位置有$p$个BETA狗。

输出格式

一行一个正整数，表示Nick最多可以干掉几个BETA狗。

样例输入 1

3 2
0 9
-4 3
0 -1

样例输出 1

9

样例输入 2

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

样例输出 2

12

样例解释

对于样例$1$，由于轨迹不能相交，那么只能由最下面的炮塔攻击位置$(1,2)$。

对于样例$2$，可以由$(2,1),(3,2),(4,4)$三个炮塔解决$5+3+4=12$个BETA狗。

数据范围

对于$20\%$的数据，$n, m\le 5$。

对于另外$20\%$的数据，最多有$2$个朝向上下的炮塔。

对于另外$20\%$的数据，最多有$6$个炮塔。

对于$100\%$的数据，$n, m\le 50$，每个位置的BETA狗数量不超过$999$个，保证不存在任意一个炮塔能够瞄准另外一个炮塔。