#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; } #define getchar getchar_unlocked inline int read(){ int x = 0; bool fl = 0; char c = getchar(); while (c >= '0' && c <= '9'){ x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x; } int main(){ scanf("%d%d",&n,&l); for(int i=1;i<=n;i++){ c[i]=read(); for(int j=1;j<=l;j++){ p[i][j]=read(); } } 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(0,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,0)]); nmax=max(nmax,dp[i]); } printf("%d",nmax); }