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