#82. 「2023 新生杯」十字切割

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: woruo

题目描述

因为 EricJC 的蹦蹦炸弹没炸死几个敌人,所以猫猫冒险队很快被怪海包围。

近距离作战已经不能用炸弹了,vivid 表示自己从 Koishi 那偷学到的十字切割将会帮猫猫冒险队杀出重围。

战斗的场地由 行, 列的地板组成。每块地板上可能是怪群,也可能是城堡的承重柱。

每块地板上都有一定的怪物数目,怪物数目为 的地板是城堡的承重柱。

vivid 可以选择任意一块没有承重柱的地板,然后进行十字切割。

十字切割的效果如下:

  • 被选中的地板会拥有十字切割的覆盖范围。
  • 从被选中的那块地板开始从上下左右四个方向直线延伸覆盖范围,直到遇到承重柱或者到达战斗场地边界停止。
  • 将十字切割覆盖范围内的所有怪物击杀。

vivid 的体力只允许她使用一次十字切割,她想知道自己最多能击杀多少怪物。

输入格式

第一行两个正整数 ,用一个空格分隔,代表战斗场地有 行, 列。

接下来 行, 每行输入 个整数 ,用一个空格分隔,代表第 行, 第 列地板上的怪物数量为

输出格式

输出一行一个正整数 ,代表 vivid 最多能击杀 只怪物。

样例

样例输入 1

3 3
1 1 1
1 0 1
0 1 1

样例输出 1

5

样例输入 2

5 5
1 9 1 1 9
1 0 1 0 1
0 9 9 9 0
0 1 0 1 1
1 1 1 0 1

样例输出 2

31

数据范围与提示

如果 ,代表第 行,第 列地板上的是承重柱。