#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=0;i<=n;i++) { long long d=0; if(i-cl2-1>=1) 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; }