Description

A 君正在玩一款战略游戏，游戏中的规则是这样的：

给定一个 $n\times m$ 的地图，地图上每一个位置要么是空地，要么是炮塔，要么有若干数量的敌人。现在 A 君要操控炮塔攻击这些敌人。

对于每个炮塔，他们的攻击方向已经确定（上下左右其中一个），A 君只需要为每个炮塔指定攻击位置。每一个炮塔只能朝它攻击方向上的某个位置进行攻击，每个炮塔只能攻击一次，当然，炮塔也可以不进行攻击。炮塔对一个位置攻击后，位置上的所有敌人都会被消灭。

现在，游戏已经保证不存在一个炮塔能够攻击另一个炮塔的情况。但是，若把炮塔的位置与其攻击位置间的连线称为炮弹的运行轨迹，那么 A 君的攻击方案要保证不存在两条轨迹相交。

在端点处（即攻击了同一个位置）也算相交，下图是一个相交的例子：

现在每个炮塔选定攻击位置（或是不攻击）后，所有炮塔将会同时开炮进行攻击，请你告诉 A 君，他一次最多可以消灭多少敌人。

Input Format

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

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

Output Format

一行一个整数表示答案。

Sample

样例输入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

Hint

$20\%$ 的数据：$n,m\leq 5$

另有 $20\%$ 的数据：最多有 $2$ 个朝向为上或下的炮塔

另有 $20\%$ 的数据：最多有 $6$ 个炮塔

$100\%$ 的数据：$1\leq n,m\leq 50$，每个位置上的敌人数量不超过 $999$，保证不存在一个炮塔可以攻击另一个炮塔