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.

题目描述

L 形管道排成 $n$ 行 $m$ 列，每个管道有 4 种摆放方式：

第 $i$ 行第 $j$ 个管道的权值为 $a_{ij}$，注意权值不一定为正。

如果两个相邻的管道接口相连，那么会产生两管道权值和的价值，但如果权值和为负数，贡献为 $0$。

你现在可以任意调整管道的摆放方式，请求出最大可能的价值和。

输入格式

• 第一行两个整数 $n, m$。
• 接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个数表示 $a_{ij}$。

输出格式

• 一个数，表示最大价值。

样例

Input 1

1 7
15 -5 100 -40 10 10 10

Output 1

115

Input 2

3 3
-10 4 -10
3 1 -10
6 2 8

Output 2

28

样例解释

样例解释 1

这是一种可能的最优方案，总价值为 $95+0+20=115$。

样例解释 2

数据范围

$1\le n,m\le 10^3,-10^3\le a_{ij}\le 10^3$。