bLue的游戏

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

这几天,bLue 在玩一款小游戏,在这个游戏中,玩家可以在一个二维地图上操作,地图中每个点都有两种可能,物品箱或墙。

玩家在一次游戏中,只有至多一次机会,可以选择一个不是墙的位置来放置炸弹。炸弹爆炸时会以炸弹自身为中心,向正上、正下、正左、正右四个方向呈十字形爆炸,墙可以挡住爆炸。

如图所示(* 表示墙,. 表示物品箱,# 表示放置炸弹的位置):

. . . * . .

. . . . . .

. * . # . .

. . . . . .

. . . . . .

爆炸能炸到的位置为(用 x 表示):

. . . * . .

. . . x . .

. * x x x x

. . . x . .

. . . x . .

玩家的初始分为 0,每个物品箱都有特定的分数,玩家可以获得所有被炸弹炸开的物品箱上的分数。

bLue 想知道他应该在什么位置放炸弹,才能获得最大分数。

Input

输入数据有多组(数据组数不超过 100)。

每组数据包含多行:

  • 第一行包含 2 个整数 n, m (0 < n, m <= 100),分别代表地图的行数和列数。
  • 接下来有 n 行,每行包含用空格隔开的 m 个整数 aij (-1 <= aij <= 100) ,代表第 i 行第 j 列处的状态,-1 表示此处是墙,否则表示此处是物品箱,数值为其可提供的分数。

n 和 m 同时为 0 时输入结束。

Output

对于每组数据,输出一行,包含一个整数,表示 bLue 能得到的最大分数。

Sample Input

3 3
1 9 2
8 3 7
2 1 2
5 6
1 2 3 -1 3 1
1 1 1 99 1 1
9 -1 8 1 5 4
1 10 1 1 1 1
1 1 1 10 3 4
0 0

Sample Output

28
128

Hint

Source

【第六届ACM趣味编程循环赛 Round #2】bLue