#include <bits/stdc++.h>

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int inf = 1e9;

int main()
{

    //freopen("input.txt", "r", stdin);

    //ios_base::sync_with_stdio(false);
    //cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int> > v(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> v[i][j];
        }
    }

    vector<vector<vector<int> > > dp(n, vector<vector<int> >(n, vector<int>(n + m - 1, -inf)));
    dp[0][0][0] = v[0][0];
    int dx[2] = {1, 0};
    int dy[2] = {0, 1};
    for (int k = 0; k < n + m - 2; ++k) {
        for (int a = 0; a < n; ++a) {
            for (int b = 0; b < n; ++b) {
                if (dp[a][b][k] != -inf) {
                    int c = k - a, d = k - b;
                    for (int i = 0; i < 2; ++i) {
                        for (int j = 0; j < 2; ++j) {
                            if (a + dx[i] < n && c + dy[i] < m && b + dx[j] < n && d + dy[j] < m) {
                                int sum = v[a + dx[i]][c + dy[i]];
                                if (a + dx[i] != b + dx[j] || c + dy[i] != d + dy[j]) {
                                    sum += v[b + dx[j]][d + dy[j]];
                                }
                                dp[a + dx[i]][b + dx[j]][k + 1] = max(dp[a + dx[i]][b + dx[j]][k + 1], dp[a][b][k] + sum);
                            }
                        }
                    }
                }
            }
        }
    }

    cout << dp[n - 1][n - 1][n + m - 2] << "\n";

}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int inf = 1e9;

int main()
{

    //freopen("input.txt", "r", stdin);

    //ios_base::sync_with_stdio(false);
    //cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int> > v(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> v[i][j];
        }
    }

    vector<vector<vector<int> > > dp(n, vector<vector<int> >(n, vector<int>(n + m - 1, -inf)));
    dp[0][0][0] = v[0][0];
    int dx[2] = {1, 0};
    int dy[2] = {0, 1};
    for (int k = 0; k < n + m - 2; ++k) {
        for (int a = 0; a < n; ++a) {
            for (int b = 0; b < n; ++b) {
                if (dp[a][b][k] != -inf) {
                    int c = k - a, d = k - b;
                    for (int i = 0; i < 2; ++i) {
                        for (int j = 0; j < 2; ++j) {
                            if (a + dx[i] < n && c + dy[i] < m && b + dx[j] < n && d + dy[j] < m) {
                                int sum = v[a + dx[i]][c + dy[i]];
                                if (a + dx[i] != b + dx[j] || c + dy[i] != d + dy[j]) {
                                    sum += v[b + dx[j]][d + dy[j]];
                                }
                                dp[a + dx[i]][b + dx[j]][k + 1] = max(dp[a + dx[i]][b + dx[j]][k + 1], dp[a][b][k] + sum);
                            }
                        }
                    }
                }
            }
        }
    }

    cout << dp[n - 1][n - 1][n + m - 2] << "\n";

}

```