#pragma GCC optimize("O2") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define int ll #define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1) #define INT128_MIN (-INT128_MAX - 1) #ifdef DEBUG #define dbg(x) cout << (#x) << " = " << x << '\n' #else #define dbg(x) #endif namespace R = std::ranges; namespace V = std::views; using namespace std; using ll = long long; using ull = unsigned long long; using ldb = long double; //#define double ldb template ostream& operator<<(ostream& os, const array &arr) { for(const T &X : arr) os << X << ' '; return os; } template ostream& operator<<(ostream& os, const vector &vec) { for(const T &X : vec) os << X << ' '; return os; } template ostream& operator<<(ostream& os, const set &s) { for(const T &x : s) os << x << ' '; return os; } void chmax(array &a, int b) { if (b >= a[0]) a[1] = a[0], a[0] = b; else if (b > a[1]) a[1] = b; } signed main() { ios::sync_with_stdio(false), cin.tie(NULL); int h, w; cin >> h >> w; vector a(h, vector(w)); for(auto &v : a) for(int &x : v) cin >> x; vector best(h, vector>(w, {-1, -1})); int ans = 0; { vector tmp(h); for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) tmp[i] += a[i][j]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) chmax(best[i][j], tmp[i]); R::sort(tmp | V::reverse); ans = max(ans, tmp[0] + tmp[1]); } { vector tmp(w); for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) tmp[j] += a[i][j]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) chmax(best[i][j], tmp[j]); R::sort(tmp | V::reverse); ans = max(ans, tmp[0] + tmp[1]); } { vector tmp(h + w - 1); for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) tmp[i + j] += a[i][j]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) chmax(best[i][j], tmp[i + j]); R::sort(tmp | V::reverse); ans = max(ans, tmp[0] + tmp[1]); } { vector tmp(h + w - 1); for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) tmp[i - j + (w - 1)] += a[i][j]; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) chmax(best[i][j], tmp[i - j + (w - 1)]); R::sort(tmp | V::reverse); ans = max(ans, tmp[0] + tmp[1]); } for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) ans = max(ans, best[i][j][0] + best[i][j][1] - a[i][j]); cout << ans << '\n'; return 0; }