← 返回题目列表

Codeforces · 429/B

B. 锻炼

中文机器翻译题面 查看原题

夏天来了! Iahub 和 Iahubina 是时候锻炼了,因为他们都想在海滩上看起来很性感。他们去的健身房是一个有n行m列的矩阵a。令数字a[i][j]表示在第i行第j列的健身房单元格中进行锻炼所消耗的卡路里。

Iahub 从位于第 1 行第 1 列的锻炼开始。他需要以锻炼 a[n][m] 结束。完成锻炼 a[i][j] 后,他可以转到锻炼 a[i + 1][j] 或 a[i][j + 1]。同样,Iahubina 从锻炼 a[n][1] 开始,她需要以锻炼 a[1][m] 结束。从单元格 a[i][j] 完成锻炼后,她转到 a[i][j + 1] 或 a[i - 1][j]。

他们的训练还有一个附加条件。他们必须在健身房的一间牢房里见面。在那个牢房里,他们都不会成功。他们会谈论快速求幂(相当奇怪的闲聊),然后他们俩都会进入下一个锻炼。

如果锻炼是由 Iahub 或 Iahubina 完成的,则计为总增益。请为 Iahub 和 Iahubina 制定锻炼计划,例如总增益尽可能大。请注意,Iahub 和 Iahubina 可以以不同的速度执行锻炼,因此它们用于到达 meet cell 的 cell 数量可能不同。

输入

输入的第一行包含两个整数 n 和 m (3 ≤ n, m ≤ 1000)。接下来的 n 行中的每一行都包含 m 个整数:第 i 行中的第 j 个数字表示元素 a[i][j] (0 ≤ a[i][j] ≤ 105)。

输出

输出包含一个数字——可能的最大总增益。

示例

输入 #1

3 3
100 100 100
100 1 100
100 100 100

输出 #1

800

注意

Iahub 将选择练习 a[1][1] → a[1][2] → a[2][2] → a[3][2] → a[3][3]。 Iahubina 将选择练习 a[3][1] → a[2][1] → a[2][2] → a[2][3] → a[1][3]。