#include<bits/stdc++.h> using namespace std; const int N=3e4+10; int n,l; int c[N]; int xl[N][15]; int yl[N][15]; int dp[N]; int xlj[15],ylj[15]; int step(int x,int y){ int ans=0; for(int i=1;i<=l;i++){ xlj[i]=xl[x][i]; ylj[i]=yl[x][i]; } for(int i=1;i<=l;i++){ int k=yl[y][i]; ans+=xlj[k]-i; for(int j=xlj[k]-1;j>=i;j--){ ylj[j+1]=ylj[j]; xlj[ylj[j]]++; } ylj[i]=k; xlj[k]=i; } return ans; } int Max[N]; 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++){ int a; scanf("%d",&a); yl[i][j]=a; xl[i][a]=j; } } for(int i=1;i<=l;i++) xl[0][i]=i; for(int i=1;i<=l;i++) yl[0][i]=i; for(int i=1;i<=n;i++){ dp[i]=INT_MIN; for(int j=max(0,i-78);j<i;j++){ if(i-j>=step(i,j)){ dp[i]=max(dp[i],dp[j]+c[i]); } } if(i>=78) dp[i]=max(dp[i],Max[i-78]); Max[i]=max(Max[i-1],dp[i]); } printf("%d",Max[n]); return 0; }