//#pragma GCC target ("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #ifdef MARC_LOCAL #define _GLIBCXX_DEBUG #endif #ifdef ATCODER #include using namespace atcoder; #endif #include using namespace std; //#define int long long using ll = long long; using vll = vector; using vvll = vector; using vvvll = vector; using vvvvll = vector; using vi = vector; using vvi = vector; using vvvi = vector; using vvvvi = vector; using ld = long double; using vld = vector; using vvld = vector; using vd = vector; using vc = vector; using vvc = vector; using vs = vector; using vb = vector; using vvb = vector; using vvvb = vector; using pii = pair; using pcc = pair; using pll = pair; using pli = pair; using pdd = pair; using pldld = pair; using vpii = vector; using vvpii = vector; using vpll = vector; using vvpll = vector; using vpldld = vector; using ui = unsigned int; using ull = unsigned long long; using i128 = __int128; using f128 = __float128; template using pqg = priority_queue, greater>; #define vec(type, name, ...) vector name(__VA_ARGS__) #define vv(type, name, h, ...) vector > name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) vector > > name(h, vector >(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) vector > > > name(a, vector > >(b, vector >(c, vector(__VA_ARGS__)))) #define overload4(a,b,c,d,name,...) name #define rep1(n) for(ll i = 0; i < (ll)n; i++) #define rep2(i,n) for(ll i = 0; i < (ll)n; i++) #define rep3(i,a,b) for (ll i = a; i < (ll)b; i++) #define rep4(i,a,b,c) for (ll i = a; i < (ll)b; i += (ll)c) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define repback1(n) for (ll i = (ll)n-1; i >= 0; i--) #define repback2(i,n) for (ll i = (ll)n-1; i >= 0; i--) #define repback3(i,a,b) for (ll i = (ll)b-1; i >= (ll)a; i--) #define repback4(i,a,b,c) for (ll i = (ll)b-1; i >= (ll)a; i -= (ll)c) #define repback(...) overload4(__VA_ARGS__,repback4,repback3,repback2,repback1)(__VA_ARGS__) #define all(x) (x).begin(), (x).end() #define include(y, x, H, W) (0 <= (y) && (y) < (H) && 0 <= (x) && (x) < (W)) #define square(x) (x) * (x) #define pb push_back #define eb emplace_back #define fir first #define sec second #define equals(a,b) (fabs((a) - (b)) < EPS) #define TIMER_START TIME_START = clock() #ifdef MARC_LOCAL // https://trap.jp/post/1224/ #define debug1(x) cout << "debug: " << (#x) << ": " << (x) << endl #define debug2(x, y) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << endl #define debug3(x, y, z) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << ", " << (#z) << ": " << (z) << endl #define debug4(x, y, z, w) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << ", " << (#z) << ": " << (z) << ", " << (#w) << ": " << (w) << endl #define debug5(x, y, z, w, v) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << ", " << (#z) << ": " << (z) << ", " << (#w) << ": " << (w) << ", " << (#v) << ": " << (v) << endl #define debug6(x, y, z, w, v, u) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << ", " << (#z) << ": " << (z) << ", " << (#w) << ": " << (w) << ", " << (#v) << ": " << (v) << ", " << (#u) << ": " << (u) << endl #define overload6(a, b, c, d, e, f, g,...) g #define debug(...) overload6(__VA_ARGS__, debug6, debug5, debug4, debug3, debug2, debug1)(__VA_ARGS__) #define debuga cerr << "a" << endl #define debugnl cout << endl #define Case(i) cout << "Case #" << (i) << ": " #define TIMECHECK cerr << 1000.0 * static_cast(clock() - TIME_START) / CLOCKS_PER_SEC << "ms" << endl #define LOCAL 1 #else #define debug1(x) void(0) #define debug2(x, y) void(0) #define debug3(x, y, z) void(0) #define debug4(x, y, z, w) void(0) #define debug5(x, y, z, w, v) void(0) #define debug6(x, y, z, w, v, u) void(0) #define debug(...) void(0) #define debuga void(0) #define debugnl void(0) #define Case(i) void(0) #define TIMECHECK void(0) #define LOCAL 0 #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); clock_t TIME_START; const long double pi = 3.1415926535897932; const long long INFL = 1000000000000000000ll; const long long INFLMAX = numeric_limits< long long >::max(); // 9223372036854775807 const int INF = 1000000000; const int INFMAX = numeric_limits< int >::max(); // 2147483647 const long double INFD = numeric_limits::infinity(); const long double EPS = 1e-9; const int mod1 = 1000000007; const int mod2 = 998244353; const vi dx1 = {1,0,-1,0}; const vi dy1 = {0,1,0,-1}; const vi dx2 = {0, 1, 1, 1, 0, -1, -1, -1, 0}; const vi dy2 = {1, 1, 0, -1, -1, -1, 0, 1, 1}; constexpr char nl = '\n'; constexpr char bl = ' '; std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) {__uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do {--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest; } __int128 parse(string &s) { __int128 ret = 0; for (int i = 0; i < (int)s.length(); i++) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret; } // for __int128 (https://kenkoooo.hatenablog.com/entry/2016/11/30/163533) template ostream& operator << (ostream& os, vector& vec) { os << "["; for (int i = 0; i<(int)vec.size(); i++) { os << vec[i] << (i + 1 == (int)vec.size() ? "" : ", "); } os << "]"; return os; } /// vector 出力 template ostream& operator << (ostream& os, pair& pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // pair 出力 template ostream& operator << (ostream& os, map& map_var) { os << "{"; for (auto itr = map_var.begin(); itr != map_var.end(); itr++) { os << "(" << itr->first << ", " << itr->second << ")"; itr++; if(itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } // map出力 template ostream& operator << (ostream& os, set& set_var) { os << "{"; for (auto itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if(itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } /// set 出力 int popcnt(unsigned long long a){ return __builtin_popcountll(a); } // ll は 64bit対応! int MSB1(unsigned long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // MSB(1), 0-indexed ( (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) ) int LSB1(unsigned long long x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } // LSB(1), 0-indexed ( (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) ) long long pow2(int n) { return 1LL << n; } long long maskbit(int n) { return (1LL << n) - 1; } bool bit_is1(long long x, int i) { return ((x>>i) & 1); } string charrep(int n, char c) { return std::string(n, c); } templatevoid UNIQUE(T& A) {sort(all(A)); A.erase(unique(all(A)), A.end());} templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } template bool chmin(T& a, const U& b){ return chmin(a, (T)b); } template bool chmax(T& a, const U& b){ return chmax(a, (T)b); } void YESNO(bool b) {if(b){cout<<"YES"<<'\n';} else{cout<<"NO"<<'\n';}} void YES() {YESNO(true);} void NO() {YESNO(false);} void yesno(bool b) {if(b){cout<<"yes"<<'\n';} else{cout<<"no"<<'\n';}} void yes() {yesno(true);} void no() {yesno(false);} void YesNo(bool b) {if(b){cout<<"Yes"<<'\n';} else{cout<<"No"<<'\n';}} void Yes() {YesNo(true);} void No() {YesNo(false);} void POSIMPOS(bool b) {if(b){cout<<"POSSIBLE"<<'\n';} else{cout<<"IMPOSSIBLE"<<'\n';}} void PosImpos(bool b) {if(b){cout<<"Possible"<<'\n';} else{cout<<"Impossible"<<'\n';}} void posimpos(bool b) {if(b){cout<<"possible"<<'\n';} else{cout<<"impossible"<<'\n';}} void FIRSEC(bool b) {if(b){cout<<"FIRST"<<'\n';} else{cout<<"SECOND"<<'\n';}} void firsec(bool b) {if(b){cout<<"first"<<'\n';} else{cout<<"second"<<'\n';}} void FirSec(bool b) {if(b){cout<<"First"<<'\n';} else{cout<<"Second"<<'\n';}} void AliBob(bool b) {if(b){cout<<"Alice"<<'\n';} else{cout<<"Bob"<<'\n';}} void TakAok(bool b) {if(b){cout<<"Takahashi"<<'\n';} else{cout<<"Aoki"<<'\n';}} int GetTime() {return 1000.0*static_cast(clock() - TIME_START) / CLOCKS_PER_SEC;} ll myRand(ll B) {return (unsigned long long)rng() % B;} template void print(const T& x, const char endch = '\n') { cout << x << endch; } template T ceil_div(T x, T y) { assert(y); return (x > 0 ? (x + y - 1) / y : x / y); } template T floor_div(T x, T y) { assert(y); return (x > 0 ? x / y : (x - y + 1) / y); } template pair divmod(T x, T y) { T q = floor_div(x, y); return {q, x - q * y}; } /// (q, r) s.t. x = q*y + r ll GCD(ll a, ll b) { if(a < b) swap(a, b); if(b == 0) return a; if(a%b == 0) return b; else return GCD(b, a%b); } ll LCM(ll a, ll b) { assert(GCD(a,b) != 0); return a / GCD(a, b) * b; } ll MOD(ll &x, const ll P) { ll ret = x%P; if(ret < 0) ret += P; return x = ret; } /// x % P を非負整数に直す ll mpow(ll x, ll n, const ll mod) { x %= mod; ll ret = 1; while(n > 0) { if(n & 1) ret = ret * x % mod; x = x * x % mod; n >>= 1; } return ret; } /// x^n % mod を計算 ll lpow(ll x, ll n) { ll ret = 1; while(n > 0){ if(n & 1) ret = ret * x; x = x * x; n >>= 1; } return ret; } /// x^nを計算 string toBinary(ll n) { if(n == 0) return "0"; assert(n > 0); string ret; while (n != 0){ ret += ( (n & 1) == 1 ? '1' : '0' ); n >>= 1; } reverse(ret.begin(), ret.end()); return ret; } /// 10進数(long long) -> 2進数(string)への変換 ll toDecimal(string S) { ll ret = 0; for(int i = 0; i < (int)S.size(); i++){ ret *= 2LL; if(S[i] == '1') ret += 1; } return ret; } /// 2進数(string) → 10進数(long long)への変換 int ceil_pow2(ll n) { int x = 0; while ((1ll << x) < n) x++; return x;} /// return minimum non-negative `x` s.t. `n <= 2**x` int floor_pow2(ll n) { int x = 0; while ((1ll << (x+1)) <= n) x++; return x;} /// return maximum non-negative `x` s.t. `n >= 2**x` // ############################ // # # // # C O D E S T A R T # // # # // ############################ void solve() { int H,W; cin >> H >> W; vvll A(H, vll(W)); rep(i,H) rep(j,W) cin >> A[i][j]; vll RS(H,0); vll CS(W,0); vll NPS(H+W-1,0); map NMS; rep(i,H) { rep(j,W) { RS[i] += A[i][j]; CS[j] += A[i][j]; NPS[i+j] += A[i][j]; NMS[i-j] += A[i][j]; } } debug(RS); debug(CS); debug(NPS); debug(NMS); ll ans = 0; // 違う方向同士 -> 必ず1箇所で交わる rep(i,H) { rep(j,W) { // i,jで交わるものを全探索 vll tmp; tmp.pb(RS[i]); tmp.pb(CS[j]); tmp.pb(NPS[i+j]); tmp.pb(NMS[i-j]); sort(all(tmp), greater()); debug(i,j,tmp); if(tmp.size()>1) { chmax(ans, tmp[0] + tmp[1] - A[i][j]); } } } // 斜めだと別方向でも被らないこともある -> i+j,i-jの偶奇が異なる時 rep(a,H+W-1) { for(auto [b,v]:NMS) { if(abs(a-b)%2==1) { chmax(ans, NPS[a] + v); } } } // 同じ方向2回 sort(all(RS),greater()); sort(all(CS),greater()); sort(all(NPS),greater()); if(H>1) chmax(ans, RS[0]+RS[1]); if(W>1) chmax(ans, CS[0]+CS[1]); if(H+W-1>1) chmax(ans, NPS[0]+NPS[1]); if(NMS.size()>1) { vll tmp; for(auto [x,v]:NMS) tmp.pb(v); sort(all(tmp), greater()); chmax(ans, tmp[0]+tmp[1]); debug(tmp); } cout << ans << nl; } signed main() { cin.tie(0); ios_base::sync_with_stdio(false); TIMER_START; //cout << fixed << setprecision(15); int tt = 1; //cin >> tt; while(tt--){ solve(); } TIMECHECK; return 0; }