You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

帖木儿的祖父送给他一个棋盘，让他练习棋艺。这个棋盘是一个网格 $a$ ，有 $n$ 行和 $m$ 列，每个单元格上都写有一个非负整数。

帖木儿的挑战是在棋盘上放置一只主教，使主教攻击的所有单元格之和为最大。主教可以向对角线的所有方向攻击，而且攻击距离没有限制。请注意，主教所在的单元格也被视为受到攻击。帮助他找出他能得到的最大和。

输入格式

每个测试用例的第一行包含整数 $n$ 和 $m$

接下来的 $n$ 行分别包含 $m$ 个整数， 第$i$ 行 的第 $j$ 个元素代表 $a_{ij}$

输出格式

输出一个整数，代表可能的最大和。

输入输出样例 #1

输入 #1

4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4

输出 #1

20

样例解释

对于样例来说，主教在这个位置上可以获得最大和

限制与约定

对于 $50\%$ 的数据，$1 \le n \le 50$ , $1 \le m \le 50$, $0 \le a_{ij} \le 1000$

对于 $100\%$ 的数据，$1 \le n \le 200$ , $1 \le m \le 200$, $0 \le a_{ij} \le 10^6$

• 时间限制: $1 s$
• 空间限制: $256 MB$