#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=15000;
const ll inf=1152921504606846976;
ll f[M*2+1],g[M*2+1];
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+2);
        F(j,0,m+m) read(a[i][j]);
    }
    C=M;
    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,C*2) f[i]=inf;
    f[C]=0;
    
    F(i,1,n){
        F(i,0,C*2) g[i]=inf;
        // DEB(SZ(g));
        F(j,0,m+m){
            F(k,m-j,C*2){
                if(j+k>C*2) break;
                g[j-m+k]=min(g[j-m+k],f[k]+a[i][j]);
                // DEB(g[C]);
            }
        }
        swap(f,g);
    }
    pr("%lld",f[C]);
    return 0;
}