#include<bits/stdc++.h> using namespace std; long long dp[30004],p[30004][21],c[30004],pre[30004],g[30004]; int main() { long long n,l; cin>>n>>l; for(long long i=1;i<=n;i++){ cin>>c[i]; for(long long j=1;j<=l;j++) cin>>p[i][j]; } for(long long i=1;i<=l;i++) p[0][i]=i; memset(dp,128,sizeof(dp)); memset(pre,128,sizeof(pre)); dp[0]=pre[0]=0; long long cl2=l*(l-1)/2; for(long long i=1;i<=n;i++){ long long d=-999999999; if(i-cl2-1>=0) d=pre[i-cl2-1]; for(long long j=max(i-cl2,0ll);j<i;j++){ for(long long k=1;k<=l;k++) for(long long v=1;v<=l;v++) if(p[i][v]==p[j][k]){g[k]=v;break;} long long cnt=0; for(long long k=1;k<=l;k++) for(long long v=1;v<k;v++) if(g[v]>g[k]) cnt++; if(cnt<=i-j) d=max(d,dp[j]); } dp[i]=d+c[i]; pre[i]=max(pre[i-1],dp[i]); } cout<<pre[n]; return 0; }