#include <bits/stdc++.h>
#define F(i, x, y) for (int i = x; i <= y; i++)
#define D(i, x, y) for (int i = x; i >= y; i--)
#define pr printf
#define mst(a,b) memset(a,b,sizeof a)
#define SZ(x) ((int)x.size())
#define ll long long
#define x first
#define y second
#define pb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
#define YN(ok) cout << (ok ? "YES" : "NO") << '\n';

#ifdef LOCAL_DEFINE
#include "bits/debug.h"
#else
    #define DEB(...)  
#endif

using namespace std;

void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) { x=0;int ch=getchar(),f=0;while(ch<'0'||ch>'9') { if (ch=='-') f=1;ch=getchar();}while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}if(f)x=-x;read(oth...);}

const int N = 35001,M=1e5,B=3e4;
const ll inf=4611686018427387900;
ll f[2][M];
vector<ll> a[N];
int n,m,C;

signed main()
{
#ifdef LOCAL_DEFINE
   freopen("temp.in", "r", stdin);
#endif
    srand(time(0));

    read(n,m);
    F(i,1,n){
        a[i].resize(m+m+1);
        F(j,0,m+m) read(a[i][j]);
    }
    DEB(C);
    // sort(a+1,a+n+1,cmp);
    random_shuffle(a+1,a+n+1);
    F(i,1,n){
        // DEB(a[i]);
    }
    F(i,0,M-1) f[0][i]=f[1][i]=inf;
    f[0][B]=0;
    int now=0;
    F(i,1,n){
        now=1-now;
        // DEB(SZ(g));
        int mx=min(12000,min(n-i,i)*m);
        F(j,-mx,mx){
            F(k,0,2*m){
                f[now][k-m+j+B]=min(f[now][k-m+j+B],f[1-now][j+B]+a[i][k]);
            }
            f[1-now][j+B]=inf;
        }
    }
    pr("%lld",f[now][B]);
    return 0;
}