#include<bits/stdc++.h> using namespace std; #define int long long int n,l,p[30005][20],c[30005],nw[20]; int dp[30005],vis[20]; int ni(int x1,int x2){ memset(vis,0,sizeof(vis)); memset(nw,0,sizeof(nw)); for(int i=1;i<=l;i++)vis[p[x1][i]]=i; for(int i=1;i<=l;i++)nw[i]=vis[p[x2][i]]; int cnt=0; for(int i=1;i<=l;i++){ for(int j=i+1;j<=l;j++){ if(nw[j]<nw[i])cnt++; } } return cnt; } signed main(){ cin>>n>>l; for(int i=1;i<=n;i++){ cin>>c[i]; for(int j=1;j<=l;j++)cin>>p[i][j]; } for(int i=1;i<=l;i++)p[0][i]=i; memset(dp,-0x3f,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;i++){ for(int j=i-1;j>=0;j--){ int cnt=ni(i,j); if(cnt<=i-j)dp[i]=max(dp[i],dp[j]+c[i]); } } cout<<dp[n]; return 0; }