#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=4;
const ll inf=1152921504606846976;
vector<ll> f,g;
vector<ll> a[N];
int n,m,C;
bool cmp(vector<ll> u,vector<ll> v){
    return u[m+m+1]<v[m+m+1];
}
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+2);
        F(j,0,m+m) read(a[i][j]);
        a[i][m+m+1]=rand()%(2*n);
    }
    C=(m*(int)sqrt(n)*3);
    DEB(C);
    sort(a+1,a+n+1,cmp);
    f.pb(0);
    F(i,1,n){
        g.clear();
        F(i,0,min(C,2*m*i)) g.pb(inf);
        // DEB(SZ(g));
        F(j,0,m+m){
            int w=SZ(f)-1;
            F(k,0,w){
                if(j+k>min(C,2*m*i)) break;
                g[j+k]=min(g[j+k],f[k]+a[i][j]);
            }
        }
        swap(f,g);
    }
    pr("%lld",f[n*m]);
    return 0;
}