#include<bits/stdc++.h> using namespace std; int a[30005][15],aa[15],bb[15],c[30005],dp[30005],t[30005]; 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]); } } t[i]=max(dp[i],t[i-1]); } cout<<t[n]; }