// Problem: No.3306 Life is Easy?
// Contest: yukicoder
// URL: https://yukicoder.me/problems/no/3306
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#line 2 "/root/AtCoder/Halc-Library/Template/Template.hpp"
#include <bits/stdc++.h>
using namespace std;

#line 8 "/root/AtCoder/Halc-Library/Template/InOut.hpp"
inline void scan() {}
inline void scan(int32_t &a) { std::cin >> a; }
inline void scan(uint32_t &a) { std::cin >> a; }
inline void scan(int64_t &a) { std::cin >> a; }
inline void scan(uint64_t &a) { std::cin >> a; }
inline void scan(char &a) { std::cin >> a; }
inline void scan(float &a) { std::cin >> a; }
inline void scan(double &a) { std::cin >> a; }
inline void scan(long double &a) { std::cin >> a; }
inline void scan(std::vector<bool> &vec) {
    for (int32_t i = 0; i < vec.size(); i++) {
        int a;
        scan(a);
        vec[i] = a;
    }
}
inline void scan(std::string &a) { std::cin >> a; }
template <class T>
inline void scan(std::vector<T> &vec);
template <class T, size_t size>
inline void scan(std::array<T, size> &vec);
template <class T, class L>
inline void scan(std::pair<T, L> &p);
template <class T, size_t size>
inline void scan(T (&vec)[size]);
template <class T>
inline void scan(std::vector<T> &vec) {
    for (auto &i : vec) scan(i);
}
template <class T>
inline void scan(std::deque<T> &vec) {
    for (auto &i : vec) scan(i);
}
template <class T, size_t size>
inline void scan(std::array<T, size> &vec) {
    for (auto &i : vec) scan(i);
}
template <class T, class L>
inline void scan(std::pair<T, L> &p) {
    scan(p.first);
    scan(p.second);
}
template <class T, size_t size>
inline void scan(T (&vec)[size]) {
    for (auto &i : vec) scan(i);
}
template <class T>
inline void scan(T &a) {
    std::cin >> a;
}
inline void in() {}
template <class Head, class... Tail>
inline void in(Head &head, Tail &...tail) {
    scan(head);
    in(tail...);
}
inline void print() { std::cout << ' '; }
inline void print(const bool &a) { std::cout << a; }
inline void print(const int32_t &a) { std::cout << a; }
inline void print(const uint32_t &a) { std::cout << a; }
inline void print(const int64_t &a) { std::cout << a; }
inline void print(const uint64_t &a) { std::cout << a; }
inline void print(const char &a) { std::cout << a; }
inline void print(const char a[]) { std::cout << a; }
inline void print(const float &a) { std::cout << a; }
inline void print(const double &a) { std::cout << a; }
inline void print(const long double &a) { std::cout << a; }
inline void print(const std::string &a) {
    for (auto &&i : a) print(i);
}
template <class T>
inline void print(const std::vector<T> &vec);
template <class T, size_t size>
inline void print(const std::array<T, size> &vec);
template <class T, class L>
inline void print(const std::pair<T, L> &p);
template <class T, size_t size>
inline void print(const T (&vec)[size]);
template <class T>
inline void print(const std::vector<T> &vec) {
    if (vec.empty()) return;
    print(vec[0]);
    for (auto i = vec.begin(); ++i != vec.end();) {
        std::cout << ' ';
        print(*i);
    }
}
template <class T>
inline void print(const std::deque<T> &vec) {
    if (vec.empty()) return;
    print(vec[0]);
    for (auto i = vec.begin(); ++i != vec.end();) {
        std::cout << ' ';
        print(*i);
    }
}
template <class T, size_t size>
inline void print(const std::array<T, size> &vec) {
    print(vec[0]);
    for (auto i = vec.begin(); ++i != vec.end();) {
        std::cout << ' ';
        print(*i);
    }
}
template <class T, class L>
inline void print(const std::pair<T, L> &p) {
    print(p.first);
    std::cout << ' ';
    print(p.second);
}
template <class T, size_t size>
inline void print(const T (&vec)[size]) {
    print(vec[0]);
    for (auto i = vec; ++i != end(vec);) {
        std::cout << ' ';
        print(*i);
    }
}
template <class T>
inline void print(const T &a) {
    std::cout << a;
}
inline void out() { std::cout << '\n'; }
template <class T>
inline void out(const T &t) {
    print(t);
    std::cout << '\n';
}
template <class Head, class... Tail>
inline void out(const Head &head, const Tail &...tail) {
    print(head);
    std::cout << ' ';
    out(tail...);
}
inline void Yes(bool i = true) { out(i ? "Yes" : "No"); }
inline void No(bool i = true) { out(i ? "No" : "Yes"); }
inline void Takahashi(bool i = true) { out(i ? "Takahashi" : "Aoki"); }
inline void Aoki(bool i = true) { out(i ? "Aoki" : "Takahashi"); }
inline void Alice(bool i = true) { out(i ? "Alice" : "Bob"); }
inline void Bob(bool i = true) { out(i ? "Bob" : "Alice"); }
inline void First(bool i = true) { out(i ? "First" : "Second"); }
inline void Second(bool i = true) { out(i ? "Second" : "First"); }
inline void Possible(bool i = true) { out(i ? "Possible" : "Impossible"); }
inline void Impossible(bool i = true) { out(i ? "Impossible" : "Possible"); }
inline void fls() { std::flush(std::cout); }
struct IOsetup {
    IOsetup() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(16);
    }
} iosetup;
#line 9 "/root/AtCoder/Halc-Library/Template/Util.hpp"
using ll = int64_t;
using ld = long double;
using ull = uint64_t;
using uint = uint32_t;
using pll = std::pair<ll, ll>;
using pii = std::pair<int32_t, int32_t>;
using vl = std::vector<ll>;
using vvl = std::vector<std::vector<ll>>;
using pdd = std::pair<ld, ld>;
using tuplis = std::array<ll, 3>;
template <class T>
using pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr ll LINF = (1LL << 62) - (1LL << 31);
constexpr int32_t INF = INT_MAX >> 1;
constexpr ll MINF = 1LL << 40;
constexpr ld DINF = std::numeric_limits<ld>::infinity();
constexpr int32_t MODD = 1000000007;
constexpr int32_t MOD = 998244353;
constexpr ld EPS = 1e-9;
constexpr ld PI = 3.1415926535897932;
const ll four[] = {0, 1, 0, -1, 0};
const ll eight[] = {0, 1, 1, 0, -1, -1, 1, -1, 0};
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    } else
        return false;
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    } else
        return false;
}
template <class T>
ll sum(const T &a) {
    return accumulate(std::begin(a), std::end(a), 0LL);
}
template <class T>
ld dsum(const T &a) {
    return accumulate(std::begin(a), std::end(a), 0.0L);
}
template <class T>
auto min(const T &a) {
    return *min_element(std::begin(a), std::end(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(std::begin(a), std::end(a));
}
#line 1 "/root/AtCoder/Halc-Library/Template/Macro.hpp"
#define _overload3(_1, _2, _3, name, ...) name
#define _overload4(_1, _2, _3, _4, name, ...) name
#define _rep1(i, n) for (int64_t i = 0; i < (n); i++)
#define _rep2(i, a, b) for (int64_t i = (a); i < (b); i++)
#define _rep3(i, a, b, c) for (int64_t i = (a); i < (b); i += (c))
#define rep(...) _overload4(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)
#define _rrep1(i, n) for (int64_t i = (n) - 1; i >= 0; i--)
#define _rrep2(i, a, b) for (int64_t i = (b) - 1; i >= (a); i--)
#define rrep(...) _overload3(__VA_ARGS__, _rrep2, _rrep1)(__VA_ARGS__)
#define each(i, ...) for (auto&& i : __VA_ARGS__)
#define all(i) std::begin(i), std::end(i)
#define rall(i) std::rbegin(i), std::rend(i)
#define len(x) ((int64_t)(x).size())
#define fi first
#define se second
#define uniq(x) x.erase(unique(all(x)), std::end(x))
#define vec(type, name, ...) vector<type> name(__VA_ARGS__);
#define vv(type, name, h, ...) std::vector<std::vector<type>> name(h, std::vector<type>(__VA_ARGS__));
#define INT(...) int32_t __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) int64_t __VA_ARGS__; in(__VA_ARGS__)
#define ULL(...) uint64_t __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) std::string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) long double __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) std::vector<type> name(size); in(name)
#define VV(type, name, h, w) std::vector<std::vector<type>> name(h, std::vector<type>(w)); in(name)
#line 2 "main.cpp"
template <class Cap, class Cost, class TotalCost>
struct NetworkSimplex {
   private:
    struct Edge {
        int to;
        Cap cap;
        Cost cost;
        int idx;
    };

    template <class E>
    struct CSR {
        struct Range {
            std::vector<E>::iterator bg, ed;
            std::vector<E>::iterator begin() const { return bg; }
            std::vector<E>::iterator end() const { return ed; }
            int size() const { return ed - bg; }
            E &operator[](int i) const { return bg[i]; }
        };
        vector<pair<int, E>> given_e;
        vector<E> e_elem;
        vector<int> pos;
        int sz;
        CSR(int n) : sz(n), pos(n + 1, 0) {}
        void add(int p, E e) {
            given_e.emplace_back(p, e);
            pos[p + 1]++;
        }
        void build() {
            for (int i = 0; i < sz; i++) pos[i + 1] += pos[i];
            e_elem.resize(pos.back());
            for (int i = 0; i < pos.back(); i++) {
                e_elem[pos[given_e[i].first]] = given_e[i].second;
                pos[given_e[i].first]++;
            }
            for (int i = sz - 1; i >= 0; i--) {
                pos[i + 1] = pos[i];
            }
            pos[0] = 0;
        }
        Range operator[](int u) {
            return Range{e_elem.begin() + pos[u], e_elem.begin() + pos[u + 1]};
        }
    };

    void add_linked(CSR<pair<int, int>> &list, int idx, int pos) {
        int last = list[idx][list[idx].size() - 1].first;
        list[idx][last].second = pos + 1;
        list[idx][list[idx].size() - 1].first = pos + 1;
        list[idx][pos + 1].first = last;
        list[idx][pos + 1].second = list[idx].size() - 1;
    }

    void erase_linked(CSR<pair<int, int>> &list, int idx, int pos) {
        int left = list[idx][pos + 1].first, right = list[idx][pos + 1].second;
        list[idx][left].second = right;
        list[idx][right].first = left;
        list[idx][pos + 1] = {-1, -1};
    }

   public:
    int n;
    TotalCost total_cost = 0;
    vector<Cap> lowers;
    vector<Cap> b;
    CSR<Edge> g;
    // vector<vector<Edge>> g;
    vector<pair<int, int>> edges;

    // b:supply-demand
    NetworkSimplex(int sz) : n(sz), g(sz), b(sz) {}

    // add supply/demand
    void add_excess(int v, Cap c) { b[v] += c; }

    // s->t l<=f<=u cost=c
    void add_edge(int s, int t, Cap l, Cap u, Cost c) {
        lowers.push_back(l);
        edges.emplace_back(-1, -1);
        total_cost += TotalCost(c) * TotalCost(l);
        b[s] -= l;
        b[t] += l;
        if (s != t) {
            edges.back() = {s, g.pos[s + 1]};
            g.add(s, {t, u - l, c, g.pos[t + 1]});
            g.add(t, {s, 0, -c, g.pos[s + 1] - 1});
        } else if (c < 0) {
            total_cost += TotalCost(c) * TotalCost(u - l);
            lowers.back() += u - l;
        }
    }

    struct FlowResult {
        bool feasible;
        TotalCost cost;
        vector<Cap> flow;
        vector<Cost> potential;
    };

    FlowResult solve() {
        int zs = g.pos[1];
        for (int i = 1; i < n; i++) {
            g.add(0, {i, 0, 0, g.pos[i + 1]});
            g.add(i, {0, 0, 0, g.pos[1] - 1});
        }
        g.build();
        vector<int> level(n);
        vector<int> iter(n);
        int mn;
        auto dfs = [&](auto self, int v, Cap f) -> Cap {
            if (b[v] < 0) {
                b[v] += f;
                return f;
            }
            if (level[v] >= mn) return 0;
            for (int &i = iter[v]; i < g[v].size(); i++) {
                Edge &e = g[v][i];
                if (e.cap == 0 || level[v] >= level[e.to]) continue;
                Cap d = self(self, e.to, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.idx].cap += d;
                    if (b[v] > 0) {
                        b[v] -= d;
                        if (b[v] == 0) return d;
                        f = min(f, b[v]);
                    } else {
                        return d;
                    }
                }
            }
            return 0;
        };
        while (true) {
            fill(level.begin(), level.end(), -1);
            fill(iter.begin(), iter.end(), 0);
            queue<int> q;
            for (int i = 0; i < n; i++) {
                if (b[i] > 0) {
                    q.push(i);
                    level[i] = 0;
                }
            }
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (auto &e : g[v]) {
                    if (e.cap > 0 && level[e.to] == -1) {
                        level[e.to] = level[v] + 1;
                        q.push(e.to);
                    }
                }
            }
            mn = n;
            for (int i = 0; i < n; i++) {
                if (b[i] < 0 && level[i] != -1) mn = min(mn, level[i]);
            }
            if (mn == n) break;
            stack<pair<int, Cap>> pos;
            for (int i = 0; i < n; i++) {
                int cnt = 0;
                if (b[i] > 0) {
                    dfs(dfs, i, b[i]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (b[i] != 0) return {false, 0, {}, {}};
        }
        fill(level.begin(), level.end(), -1);
        for (int i = 0; i < n; i++) {
            if (level[i] != -1) continue;
            while (true) {
                fill(iter.begin(), iter.end(), -1);
                stack<int> pos;
                iter[i] = 0;
                pos.push(i);
                vector<pair<int, int>> cycle;
                while (!pos.empty()) {
                    int v = pos.top();
                    level[v] = 0;
                    int used = -1;
                    if (pos.size() > 1) {
                        pos.pop();
                        used = g[pos.top()][iter[pos.top()]].idx;
                        pos.push(v);
                    }
                    bool flg = false;
                    for (int &j = iter[v]; j < g[v].size(); j++) {
                        Edge &e = g[v][j];
                        if (e.cap == 0 || g[e.to][e.idx].cap == 0 || j == used)
                            continue;
                        if (iter[e.to] == -1) {
                            iter[e.to] = 0;
                            pos.push(e.to);
                            flg = true;
                            break;
                        }
                        if (iter[e.to] < g[e.to].size()) {
                            while (true) {
                                int nv = pos.top();
                                cycle.emplace_back(nv, iter[nv]);
                                pos.pop();
                                if (nv == e.to) break;
                            }
                            break;
                        }
                    }
                    if (!cycle.empty()) break;
                    if (flg) continue;
                    pos.pop();
                    if (pos.empty()) break;
                    iter[pos.top()]++;
                }
                if (cycle.empty()) break;
                Cost sm = 0;
                Cap mn = numeric_limits<Cap>::max();
                for (auto &p : cycle) {
                    Edge &e = g[p.first][p.second];
                    sm += e.cost;
                    mn = min(mn, e.cap);
                }
                if (sm <= 0) {
                    for (auto &p : cycle) {
                        Edge &e = g[p.first][p.second];
                        e.cap -= mn;
                        g[e.to][e.idx].cap += mn;
                    }
                } else {
                    mn = numeric_limits<Cap>::max();
                    for (auto &p : cycle) {
                        Edge &e = g[p.first][p.second];
                        mn = min(mn, g[e.to][e.idx].cap);
                    }
                    for (auto &p : cycle) {
                        Edge &e = g[p.first][p.second];
                        e.cap += mn;
                        g[e.to][e.idx].cap -= mn;
                    }
                }
            }
        }
        CSR<pair<int, int>> tree(n);
        for (int i = 0; i < n; i++) {
            tree.add(i, {-1, g[i].size() + 1});
            rep(_, g[i].size()) { tree.add(i, {-1, -1}); }
            tree.add(i, {0, -1});
        }
        tree.build();
        fill(level.begin(), level.end(), -1);
        vector<Cost> p(n, 0);
        vector<int> parent(n, -1);
        vector<pair<int, int>> can;
        for (int i = 0; i < n; i++) {
            if (level[i] != -1) continue;
            stack<int> q;
            q.push(i);
            if (i == 0)
                level[i] = 0;
            else
                level[i] = 1;
            p[i] = 0;
            if (i != 0) {
                parent[i] = g[0][zs + i - 1].idx;
                add_linked(tree, 0, zs + i - 1);
                add_linked(tree, g[0][zs + i - 1].to, g[0][zs + i - 1].idx);
            }
            while (!q.empty()) {
                int v = q.top();
                q.pop();
                for (int i = 0; i < g[v].size(); i++) {
                    Edge &e = g[v][i];
                    if (e.cap == 0 || g[e.to][e.idx].cap == 0 ||
                        level[e.to] != -1) {
                        if (e.cap != 0) {
                            if (g[e.to][e.idx].cap == 0)
                                can.emplace_back(v, i);
                            else
                                parent[v] = i;
                        }
                        continue;
                    }
                    level[e.to] = level[v] + 1;
                    p[e.to] = p[v] + e.cost;
                    q.push(e.to);
                    add_linked(tree, v, i);
                    add_linked(tree, e.to, e.idx);
                }
            }
        }
        while (true) {
            pair<Cost, int> mn = {numeric_limits<Cost>::max(), -1};
            for (int i = 0; i < can.size(); i++) {
                Edge &e = g[can[i].first][can[i].second];
                if (e.cap == 0) continue;
                mn = min(mn, {e.cost + p[can[i].first] - p[e.to], i});
            }
            if (mn.first >= 0) break;
            vector<int> gl = {can[mn.second].first};
            int st = g[can[mn.second].first][can[mn.second].second].to;
            vector<pair<int, int>> ncyc = {can[mn.second]};
            while (st != gl.back()) {
                if (level[st] < level[gl.back()]) {
                    gl.emplace_back(g[gl.back()][parent[gl.back()]].to);
                } else {
                    ncyc.emplace_back(st, parent[st]);
                    st = g[st][parent[st]].to;
                }
            }
            for (int i = gl.size() - 2; i >= 0; i--) {
                ncyc.emplace_back(gl[i + 1], g[gl[i]][parent[gl[i]]].idx);
            }
            Cap mc = numeric_limits<Cap>::max();
            for (auto &i : ncyc) mc = min(mc, g[i.first][i.second].cap);
            int del = -1;
            for (int i = 0; i < ncyc.size(); i++) {
                Edge &e = g[ncyc[i].first][ncyc[i].second];
                e.cap -= mc;
                if (e.cap == 0) del = i;
                g[e.to][e.idx].cap += mc;
            }
            if (del == 0) {
                can[mn.second] = {
                    g[can[mn.second].first][can[mn.second].second].to,
                    g[can[mn.second].first][can[mn.second].second].idx};
                continue;
            }
            erase_linked(tree, ncyc[del].first, ncyc[del].second);
            erase_linked(tree, g[ncyc[del].first][ncyc[del].second].to,
                         g[ncyc[del].first][ncyc[del].second].idx);
            add_linked(tree, can[mn.second].first, can[mn.second].second);
            add_linked(tree, g[can[mn.second].first][can[mn.second].second].to,
                       g[can[mn.second].first][can[mn.second].second].idx);
            can[mn.second] = {g[ncyc[del].first][ncyc[del].second].to,
                              g[ncyc[del].first][ncyc[del].second].idx};
            fill(level.begin(), level.end(), -1);
            level[0] = 0;
            stack<int> q;
            q.push(0);
            while (!q.empty()) {
                int v = q.top();
                q.pop();
                int pos = 0;
                while (true) {
                    int np = tree[v][pos].second;
                    pos = np;
                    np--;
                    if (np >= g[v].size()) break;
                    Edge &e = g[v][np];
                    if (level[e.to] != -1) {
                        parent[v] = np;
                        continue;
                    }
                    p[e.to] = p[v] + e.cost;
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }

        for (int i = 0; i < edges.size(); i++) {
            int s = edges[i].first, t = edges[i].second;
            if (s == -1) continue;
            Edge &e = g[s][t];
            lowers[i] += g[e.to][e.idx].cap;
            total_cost += TotalCost(e.cost) * TotalCost(g[e.to][e.idx].cap);
        }
        return {true, total_cost, lowers, p};
    }
};

void solve() {
    LL(N,M);
    VV(ll,A,N,M);
    ll day=N/2;
    NetworkSimplex<ll,ll,ll> gr(day*2);
    if(N==1){
    	ll ans=0;
    	rep(i,day){
    		ans+=A[N-i-1][0]-A[i][0];
    	}
    	out(ans);
    	return;
    }
    if(N==2){
    	vl s1,s2;
    	ll ans=0;
    	rep(i,day){
    		ans+=A[N-i-1][0]-A[i][0];
    		s1.push_back(A[N-i-1][1]-A[N-i-1][0]);
    		s2.push_back(A[i][0]-A[i][1]);
    	}
    	sort(all(s1));
    	sort(all(s2));
    	ll fin=ans;
    	rrep(i,day){
    		ans+=s1[i]+s2[i];
    		chmax(fin,ans);
    	}
    	out(fin);
    	return;
    }
    rep(i,day){
    	rep(j,day){
    		ll mx=0;
    		rep(k,M){
    			chmax(mx,A[N-j-1][k]-A[i][k]);
    		}
    		gr.add_edge(i,j+day,0,1,-mx);
    	}
    	gr.add_excess(i,1);
    	gr.add_excess(i+day,-1);
    }
    out(-gr.solve().cost);
}
int main() { solve(); }