#include "bits/stdc++.h"
using namespace std;

const int N = 205;

int n, m;
int arr[N][N];
int dp[N][N][N];

int dx[] = {0, 1};
int dy[] = {1, 0};

inline bool isValid(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < m);
}

inline int solve(int a1, int b1, int a2) {
    int b2 = (a1 + b1) - (a2);
    if (dp[a1][b1][a2] != -1) {
        return dp[a1][b1][a2];
    }
    if ((a1 == a2) && (b1 == b2)) {
        if ((a1 + b1 > 0) && (a1 + b1 < n + m - 2)) {
            return 0;
        }
    }
    if (a1 == n - 1 && b1 == m - 1) {
        return dp[a1][b1][a2] = arr[a1][b1];
    }
    int score = arr[a1][b1];
    if (a1 != a2 || b1 != b2) {
        score += arr[a2][b2];
    }
    int result = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            int na1 = a1 + dx[i];
            int nb1 = b1 + dy[i];
            int na2 = a2 + dx[j];
            int nb2 = b2 + dy[j];
            if (isValid(na1, nb1) && isValid(na2, nb2)) {
                result = max(result, solve(na1, nb1, na2));
            }
        }
    }
    return dp[a1][b1][a2] = result + score;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    memset(dp, -1, sizeof dp);
    cout << solve(0, 0, 0) << endl;
}
### Prompt

In cpp, your task is to solve the following problem:

Input

The input is given from standard input in the following format.


> $H \ W$ $a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}$ $a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $a_{H, 1} \ a_{H, 2} \ \cdots \ a_{H, W}$

Output

* Print the maximum number of souvenirs they can get.



Constraints

* $1 \le H, W \le 200$
* $0 \le a_{i, j} \le 10^5$



Subtasks

Subtask 1 [ 50 points ]


* The testcase in the subtask satisfies $1 \le H \le 2$.

Subtask 2 [ 80 points ]


* The testcase in the subtask satisfies $1 \le H \le 3$.

Subtask 3 [ 120 points ]


* The testcase in the subtask satisfies $1 \le H, W \le 7$.

Subtask 4 [ 150 points ]


* The testcase in the subtask satisfies $1 \le H, W \le 30$.

Subtask 5 [ 200 points ]


* There are no additional constraints.

Output

* Print the maximum number of souvenirs they can get.



Constraints

* $1 \le H, W \le 200$
* $0 \le a_{i, j} \le 10^5$



Subtasks

Subtask 1 [ 50 points ]


* The testcase in the subtask satisfies $1 \le H \le 2$.

Subtask 2 [ 80 points ]


* The testcase in the subtask satisfies $1 \le H \le 3$.

Subtask 3 [ 120 points ]


* The testcase in the subtask satisfies $1 \le H, W \le 7$.

Subtask 4 [ 150 points ]


* The testcase in the subtask satisfies $1 \le H, W \le 30$.

Subtask 5 [ 200 points ]


* There are no additional constraints.

Input

The input is given from standard input in the following format.


> $H \ W$ $a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}$ $a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $a_{H, 1} \ a_{H, 2} \ \cdots \ a_{H, W}$

Examples

Input

3 3
1 0 5
2 2 3
4 2 4


Output

21


Input

6 6
1 2 3 4 5 6
8 6 9 1 2 0
3 1 4 1 5 9
2 6 5 3 5 8
1 4 1 4 2 1
2 7 1 8 2 8


Output

97

### Response

```cpp
#include "bits/stdc++.h"
using namespace std;

const int N = 205;

int n, m;
int arr[N][N];
int dp[N][N][N];

int dx[] = {0, 1};
int dy[] = {1, 0};

inline bool isValid(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < m);
}

inline int solve(int a1, int b1, int a2) {
    int b2 = (a1 + b1) - (a2);
    if (dp[a1][b1][a2] != -1) {
        return dp[a1][b1][a2];
    }
    if ((a1 == a2) && (b1 == b2)) {
        if ((a1 + b1 > 0) && (a1 + b1 < n + m - 2)) {
            return 0;
        }
    }
    if (a1 == n - 1 && b1 == m - 1) {
        return dp[a1][b1][a2] = arr[a1][b1];
    }
    int score = arr[a1][b1];
    if (a1 != a2 || b1 != b2) {
        score += arr[a2][b2];
    }
    int result = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            int na1 = a1 + dx[i];
            int nb1 = b1 + dy[i];
            int na2 = a2 + dx[j];
            int nb2 = b2 + dy[j];
            if (isValid(na1, nb1) && isValid(na2, nb2)) {
                result = max(result, solve(na1, nb1, na2));
            }
        }
    }
    return dp[a1][b1][a2] = result + score;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    memset(dp, -1, sizeof dp);
    cout << solve(0, 0, 0) << endl;
}
```