#include<bits/stdc++.h> using namespace std; int a[30005][12],aa[15],bb[15],c[300005],dp[300005],t[300005]; int tree[15],ans; int n,l; int lowbit(int x){ return x&(-x); } void add(int x,int v){ for(;x<=n;){ tree[x]+=v; x+=lowbit(x); } } int ask(int x){ int ans=0; for(;x>=1;){ ans+=tree[x]; x-=lowbit(x); } return ans; } int check(int x,int y){ ans=0; for(int i=1;i<=l;i++){ tree[i]=0; bb[a[x][i]]=i; } for(int i=1;i<=l;i++){ aa[i]=bb[a[y][i]]; // cout<<aa[i]<<' '; } for(int i=1;i<=l;i++){ add(aa[i],1); ans+=i-ask(aa[i]); } return ans; } int main(){ cin>>n>>l; for(int i=1;i<=n;i++){ cin>>c[i]; for(int j=1;j<=l;j++){ cin>>a[i][j]; } } for(int i=1;i<=l;i++) a[0][i]=i; dp[0]=0; for(int i=1;i<=n;i++){ for(int j=max(0,i-l*l);j<i;j++){ //cout<<check(i,j)<<' '<<i-j<<' '<<i<<' '<<j<<'\n'; if(check(i,j)<=i-j){ dp[i]=max(dp[i],dp[j]+c[i]); } else{ dp[i]=max(dp[i],dp[j]); } } if(1<=i-l*l) dp[i]=max(dp[i],t[i-l*l-1]+c[i]); t[i]=max(dp[i],t[i-1]); } cout<<t[n]; }