#include<bits/stdc++.h> using namespace std; long long n,l,c[300004],p[300004][20],dp[300004],t[20]; inline long long ck(long long a,long long b){ for(int i=1;i<=l;i++){ t[p[a][i]]=i; } long long sum=0; for(int i=1;i<=l;i++){ for(int j=1;j<i;j++){ if(t[p[b][j]]>t[p[b][i]])sum++; } } if(b-a>=sum){ return 1; } return 0; } int main(){ scanf("%lld%lld",&n,&l); for(int i=1;i<=n;i++){ scanf("%lld",&c[i]); for(int j=1;j<=l;j++){ scanf("%lld",&p[i][j]); } } for(int i=1;i<=l;i++){ p[0][i]=i; } if(l==2){ long long sum=0; for(int i=1;i<=n;i++){ sum+=c[i]; } printf("%lld\n",sum); return 0; } memset(dp,0x80,sizeof(dp)); dp[0]=0; long long qjmax=0; long long nmax=0; for(int i=1;i<=n;i++){ for(int j=i-1;j>=max(0ll,i-l*l-2);j--){ if(ck(j,i)){ dp[i]=max(dp[i],dp[j]+c[i]); } } if(i>=l*l+10)dp[i]=max(dp[i],qjmax+c[i]); qjmax=max(qjmax,dp[max(i-l*l,0ll)]); nmax=max(nmax,dp[i]); } printf("%lld",nmax); }