#include #include #include #include using namespace std; using u64 = long long; int n, m; int hamster[1001][1001]; bool visited[1001][1001]{}; struct result { int sum; bool success; }; result dfs(int x, int y) { if (x < 0 || y < 0 || x >= n || y >= m) { return { 0, false }; } if (visited[x][y]) { return { 0, false }; } if (x == n - 1 && y == n - 1) { return { hamster[x][y], true }; } int best = 0; bool success = false; visited[x][y] = true; result res = dfs(x + 1, y); if (res.success) { best = std::max(best, res.sum); success = true; } res = dfs(x, y + 1); if (res.success) { best = std::max(best, res.sum); success = true; } res = dfs(x - 1, y); if (res.success) { best = std::max(best, res.sum); success = true; } res = dfs(x, y - 1); if (res.success) { best = std::max(best, res.sum); success = true; } visited[x][y] = false; return { best + hamster[x][y], success }; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; u64 sum = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> hamster[i][j]; sum += hamster[i][j]; } } if (n % 2 == 1 || m % 2 == 1) { printf("%llu\n", sum); return 0; } result res = dfs(0, 0); printf("%d\n", res.sum); }