Maximum Coins Collection by Two Agents

You are given a grid with n rows and m columns. Each cell in the grid contains a certain number of coins. Two agents, say Tom and Jerry, start simultaneously at the top-left cell (0,0) and move towards the bottom-right cell (n-1, m-1). Each agent can only move either right or down at every step. They collect the coins in the cells they pass through; however, if both agents land on the same cell, the coins in that cell are only counted once.

Your task is to compute the maximum total number of coins both agents can collect under the condition that they meet at the destination cell.

The problem can be formulated mathematically as follows:

Let \( grid[i][j] \) denote the number of coins at cell \( (i, j) \). Define a function \( dp(x_1, y_1, x_2, y_2) \) representing the maximum coins collected when one agent is at \( (x_1, y_1) \) and the other is at \( (x_2, y_2) \), with both having taken the same number of steps. The recurrence is given by:

[ \text{dp}(x_1,y_1,x_2,y_2) = grid[x_1][y_1] + \begin{cases} 0, & \text{if } (x_1,y_1) = (x_2,y_2)\ grid[x_2][y_2], & \text{otherwise} \end{cases} + \max\begin{cases} \text{dp}(x_1+1,y_1,x_2+1,y_2),\ \text{dp}(x_1+1,y_1,x_2,y_2+1),\ \text{dp}(x_1,y_1+1,x_2+1,y_2),\ \text{dp}(x_1,y_1+1,x_2,y_2+1)\end{cases} ]

with the base condition being that when both agents reach \( (n-1, m-1) \), the function returns \( grid[n-1][m-1] \>.

Note: You are required to read the input from stdin and output the result to stdout.

inputFormat

The first line of input contains two integers n and m, representing the number of rows and columns of the grid, respectively.

This is followed by n lines, each containing m integers separated by spaces, where the j-th integer in the i-th line represents grid[i][j], the coins in that cell.

outputFormat

Output a single integer representing the maximum number of coins that can be collected by both agents, under the condition that they meet at the bottom-right cell.

## sample

3 4
1 2 3 0
0 0 5 2
1 1 0 2

17