#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=3e4+10; int n,l,c[maxn],p[maxn][15],f[maxn],id[15],mmax=-2147483647; signed main(){ cin>>n>>l; for(int i=1;i<=l;i++)p[0][i]=i; for(int i=1;i<=n;i++)f[i]=-2147483647; for(int i=1;i<=n;i++){ cin>>c[i]; for(int j=1;j<=l;j++)cin>>p[i][j]; } f[0]=0; for(int i=1;i<=n;i++){ f[i]=max(mmax+c[i],f[i]); for(int j=max(0ll,i-l*l);j<i;j++){ int cnt=0; for(int k=1;k<=l;k++){ for(int m=1;m<=l;m++){ if(p[i][k]==p[j][m]){ id[k]=m; break; } } } for(int k=1;k<=l;k++){ for(int m=k+1;m<=l;m++){ if(id[m]<id[k])cnt++; } } if(cnt<=i-j)f[i]=max(f[i],f[j]+c[i]); } if(i>l*l)mmax=max(mmax,f[i]); //cout<<f[i]<<endl; } int ans=0; for(int i=1;i<=n;i++)ans=max(ans,f[i]); cout<<ans; }