#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
mt19937 _rand(time(0)^clock());
const int L=2500;
ll dp[2][2*L+1];
int a[35005][7];
int id[35005];
int n,k;
inline void Min(ll &a,ll b)
{
    if(b<a) a=b;
}
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++) for(int j=0;j<=2*k;j++) a[i][j]=read();
    for(int i=1;i<=n;i++) id[i]=i;
    shuffle(id+1,id+n+1,_rand);

    int now=0,lst=1;
    memset(dp[now],0x3f,sizeof(dp[now])),dp[now][L]=0;

    for(int i=1;i<=n;i++)
    {
        swap(now,lst);int p=id[i];
        memset(dp[now],0x3f,sizeof(dp[now]));
        
        for(int j=0,d=-k;j<=2*k;j++,d++) for(int i=0;i<=2*L;i++)
            if(i+d>=0&&i+d<=2*L) Min(dp[now][i+d],dp[lst][i]+a[p][j]);

        // printf("p=%d\n",p);
        // for(int j=0;j<=2*L;j++) printf("dp[%d][%2d]=%lld\n",p,j-L,dp[now][j]);
    }
    printf("%lld\n",dp[now][L]);
    return 0;
}
/*
3 1
 3 14 15
 -3 -5 -35
 2 71 82
 */