Working out

题意翻译

# 题目描述 夏天要到了，小西和小瓜决定去健身。健身房是一个n行m列的矩阵。 a[i][j]代表在第i行第j列，可以消耗的卡路里。 小西从第1行第1列出发，要到(n,m);小西可以从a[i][j]，走到a[i+1][j],或者a[i][j+1]; 小瓜从(n,1)出发，要到(1,m);小瓜可以从a[i][j]出发，走到a[i-1][j],或者a[i][j+1]; 由于小西和小瓜要聚在一起发张自拍，他们必须在健身房的某一行，某一列相遇。由于他们没有好好健身，所以在自拍地点的卡路里消耗不计入总卡路里消耗值。 如果小西和小瓜中任何一个人完成了健身，则健身结束。你的任务是求出小西和小瓜可以消耗的最大总卡路里值。 另外，他们的健身速度不同，所以可以走过的路线长度也不同。 # 输入输出格式 ## 输入格式： 第一行包含两个整数，n,m(3<=n,m<=1000)，代表健身房的行、列数，接下来的i行j列代表a[i][j]，即在第i行，j列可以燃烧的卡路里。 ## 输出格式： 输出一个整数：即他们可能消耗的总卡路里的最大值。 # 说明 对于样例1，小西可以选择： a[1][1]→a[1][2]→a[2][2]→a[3][2]→a[3][3] . 小瓜可以选择： a[3][1]→a[2][1]→a[2][2]→a[2][3]→a[1][3] .

题目描述

Summer is coming! It's time for Iahub and Iahubina to work out, as they both want to look hot at the beach. The gym where they go is a matrix $ a $ with $ n $ lines and $ m $ columns. Let number $ a[i][j] $ represents the calories burned by performing workout at the cell of gym in the $ i $ -th line and the $ j $ -th column. Iahub starts with workout located at line $ 1 $ and column $ 1 $ . He needs to finish with workout $ a[n][m] $ . After finishing workout $ a[i][j] $ , he can go to workout $ a[i+1][j] $ or $ a[i][j+1] $ . Similarly, Iahubina starts with workout $ a[n][1] $ and she needs to finish with workout $ a[1][m] $ . After finishing workout from cell $ a[i][j] $ , she goes to either $ a[i][j+1] $ or $ a[i-1][j] $ . There is one additional condition for their training. They have to meet in exactly one cell of gym. At that cell, none of them will work out. They will talk about fast exponentiation (pretty odd small talk) and then both of them will move to the next workout. If a workout was done by either Iahub or Iahubina, it counts as total gain. Please plan a workout for Iahub and Iahubina such as total gain to be as big as possible. Note, that Iahub and Iahubina can perform workouts with different speed, so the number of cells that they use to reach meet cell may differs.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $ ( $ 3<=n,m<=1000 $ ). Each of the next $ n $ lines contains $ m $ integers: $ j $ -th number from $ i $ -th line denotes element $ a[i][j] $ ( $ 0<=a[i][j]<=10^{5} $ ).

输出格式

The output contains a single number — the maximum total gain possible.

输入输出样例

输入样例 #1

3 3
100 100 100
100 1 100
100 100 100

输出样例 #1

800

说明

Iahub will choose exercises $ a[1][1]→a[1][2]→a[2][2]→a[3][2]→a[3][3] $ . Iahubina will choose exercises $ a[3][1]→a[2][1]→a[2][2]→a[2][3]→a[1][3] $ .