#include using namespace std; const long long INF = 3LL << 59; // https://judge.yosupo.jp/submission/201242 vector hungarian(int n, const vector > &a) { vector p(n), q(n); for (int i = 0; i < n; i++) { p[i] = i; q[i] = i; } vector h(n); for (int i = 1; i < n; i++) { vector d(n, INF); vector pre(n, -1); for (int j = 0; j < i; j++) { d[q[j]] = a[i][j] - a[q[j]][j] - h[q[j]]; pre[q[j]] = i; } vector used(n, false); for (int j = 0; j < i; j++) { long long mind = INF; int v = -1; for (int k = 0; k < i; k++) { if (!used[k] && mind > d[k]) { mind = d[k]; v = k; } } used[v] = true; for (int k = 0; k < i; k++) { long long nd = d[v] + a[v][k] - a[q[k]][k] - (h[q[k]] - h[v]); if (d[q[k]] > nd) { d[q[k]] = nd; pre[q[k]] = v; } } } long long best = a[i][i]; int pos = -1; for (int j = 0; j < i; j++) { if (best > d[j] + h[j] + a[j][i]) { best = d[j] + h[j] + a[j][i]; pos = j; } } for (int j = 0; j < i; j++) { h[j] += d[j]; } int nxt = i; while (pos != -1) { q[nxt] = pos; swap(nxt, p[pos]); pos = pre[pos]; } } return p; } int main(){ int n, m; cin >> n >> m; vector> a(n, vector(m)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> a[i][j]; } } int d = n / 2; if(m == 1){ long long ans = 0; for(int i = 0; i < d; i++){ ans -= a[i][0]; ans += a[i + d + n % 2][0]; } cout << ans << endl; return 0; }else if(m == 2){ vector> dp1(d + 1, vector(d + 1, INF)), dp2(d + 1, vector(d + 1, -INF)); dp1[0][0] = dp2[0][0] = 0; for(int i = 0; i < d; i++){ for(int j = 0; j <= i; j++){ dp1[i + 1][j] = min(dp1[i + 1][j], dp1[i][j] + a[i][0]); dp1[i + 1][j + 1] = min(dp1[i + 1][j + 1], dp1[i][j] + a[i][1]); } } for(int i = 0; i < d; i++){ for(int j = 0; j <= i; j++){ dp2[i + 1][j] = max(dp2[i + 1][j], dp2[i][j] + a[i + d + n % 2][0]); dp2[i + 1][j + 1] = max(dp2[i + 1][j + 1], dp2[i][j] + a[i + d + n % 2][1]); } } long long ans = 0; for(int i = 0; i <= d; i++){ ans = max(ans, dp2[d][i] - dp1[d][i]); } cout << ans << endl; return 0; } vector> w(d, vector(d, 0)); for(int i = 0; i < d; i++){ for(int j = 0; j < d; j++){ long long val = 0; for(int k = 0; k < m; k++){ val = max(val, a[j + d + n % 2][k] - a[i][k]); } w[i][j] = val * -1; } } auto res = hungarian(d, w); long long ans = 0; for(int i = 0; i < d; i++){ ans += w[i][res[i]] * -1; } cout << ans << endl; }