SLIDE - Team Slide Treasure Hunt Race


Alice and Bob are participating in an exciting new Olympic event, the Team Slide Treasure Hunt Race! This event takes place on a slide with various treasures on it, which is up to 10m wide and 10km long. Yes, that's kilometers.

The slide can be represented as a grid of cells, with $N$ ($2 \leq N \leq 10^4$) rows and $M$ ($2 \leq M \leq 10$) columns. The rows are numbered $1, 2 \ldots N$ from top to bottom, and the columns are numbered $1, 2 \ldots M$ from left to right. The cell in row $i$ and column $j$ is referred to as cell ($i$, $j$), and contains a treasure with value $G_{i,j}$ ($1 \le G_{i,j} \le 10^5$).

The two friends will each get to travel once down the slide, one after another. First, Alice will slide from the top-left corner of the slide (cell ($1$, $1$)) down to the bottom-left corner (cell ($N$, $1$)). Then, Bob will slide from the top-right corner (cell ($1$, $M$)) down to the bottom-right corner (cell ($N$, $M$)). Whenever a person moves in the slide, they move from their current row to the next row down, and they can also guide themselves left or right by one column if desired. This means that they can go from cell ($i$, $j$) to either cell ($i+1$, $j-1$), ($i+1$, $j$), or ($i+1$, $j+1$), as long as they don't exit the slide. Throughout the race, both Alice and Bob collect the treasure in each cell they slide through - this includes their respective starting and ending cells. However, if Bob goes through any cell that Alice has already visited, he can't collect the treasure in it again.

Alice and Bob would like to determine a sliding plan to allow them to collect as much treasure as possible, and win the gold medal! They've asked you to determine the maximum total value of treasure that they can collect, out of all valid strategies.

Input

The first line of the input will contain two integers $N$ and $M$, separated by a space. Each of the next $N$ lines, for $i$ from $1$ to $N$, will contain the $M$ space-separated integers $G_{i,1} \,\,\, G_{i,2} \,\,\, \dots \,\,\, G_{i, M}$.

Output

Output one number on a line by itself: the maximum combined treasure value that Alice and Bob can collect.

Example

Input:
5 4
3 6 8 2
5 2 4 3
1 1 20 10
1 1 20 10
1 1 20 10 Output: 73

Explanation of Sample

The single optimal sliding plan involves Alice sliding down-right, down-right, down-left, and down-left, followed by Bob sliding down-left, down-right, down-left, and down-right. The treasures collected are shown in bold on the following grid:

Alice collects a total treasure value of $3+2+20+1+1=27$, while Bob collects $2+4+10+20+10=46$. Their total is then $27+46=73$.


hide comments
farhad chowdhury: 2016-05-08 22:47:15

wa any critical cases plz share

CKA: 2015-08-09 12:09:06

14854935 Plz look and suggest where am I making mistake

mr_lazy: 2015-07-28 23:33:25

AC in one go!

parijat bhatt: 2015-06-03 07:20:45

Easy but silly mistakes cost me a wrong answer and a few CE.

Naman Goyal: 2015-05-26 21:11:09

Good problem. Really worth the time.

Naman Goyal: 2015-05-26 18:40:25

Sorry my bad, I read the problem top left to bottom right corner.

Last edit: 2015-05-26 20:58:47
YoungMoon KO: 2014-07-25 05:42:33

According to the problem description, "... they can go from cell (i, j) to either cell (i+1, j−1), (i+1, j), or (i+1, j+1) ...", with this movement, for the sample, Alce sliging down right,down right, down, down, down (3 + 2+ 20 + 20 + 20 = 65). For Bob sliding down left, down right, down, down, down (2 + 4+ 10 + 10 + 10 = 36). So the optimal combined max should be l01. Am I right?

RE: Read the problem more carefully.

Last edit: 2014-07-30 20:12:09
Archit Jain: 2014-07-19 22:11:54

wa again and again
author plz check 11980797

RE: Yup, it's wrong.

Last edit: 2014-07-24 17:00:53
Rishav Goyal: 2014-02-16 01:07:40

Really nice problem.

Aman Gupta: 2013-06-30 19:24:21

Nice question! Somewhat like TOURIST


Added by:SourSpinach
Date:2013-05-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem