#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=5010; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} int n,m,ans,k,S,num,a[MAXN][MAXN];bool B=1; struct tpr{ int p[MAXN],sum; void init(){ for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){ p[a[i][j]]++,num+=p[a[i][j]]==1; if(p[a[i][j]]>1&&a[i][j]!=1)B=0; S=max(S,a[i][j]); } } void upd(int x,int y){ // cout<<"U"<<x<<" "<<y<<endl; sum-=p[x]==0; p[x]-=y; sum+=p[x]==0; } void qry(){ans=max(ans,sum); // cout<<"Q"<<sum<<endl; } }T; void slvb(){ } int xl[MAXN],yl[MAXN],xr[MAXN],yr[MAXN],cs[MAXN]; void dfs(int i,int sum,int l,int r,int L,int R){ if(i==S+1){ ans=max(ans,sum); return; } dfs(i+1,sum,l,r,L,R); l=min(l,xl[i]); r=max(r,xr[i]); L=min(L,yl[i]); R=max(R,yr[i]); cs[i]=1; if((R-L+1)*(r-l+1)<=k)dfs(i+1,sum+1,l,r,L,R); cs[i]=0; } void slvs(){ memset(xl,0x3f,sizeof(xl)); memset(yl,0x3f,sizeof(yl)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) xl[a[i][j]]=min(xl[a[i][j]],i), yl[a[i][j]]=min(yl[a[i][j]],j), xr[a[i][j]]=max(xr[a[i][j]],i), yr[a[i][j]]=max(yr[a[i][j]],j); dfs(1,0,n,1,m,1); printf("%lld",num-ans); } void slv(){ n=read(),m=read(),k=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)a[i][j]=read(); T.init(); if(S<=20){slvs();return;} // return; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int now=min(j+k-1,m); for(int o=j;o<=now;o++)T.upd(a[i][o],1); T.qry(); for(int l=i+1;l<=min(n,i+k-1);l++){ int nnow=min(m,j+k/(l-i+1)-1); for(int o=j;o<=nnow;o++)T.upd(a[l][o],1); for(int o=nnow+1;o<=now;o++)for(int p=i;p<l;p++)T.upd(a[p][o],-1); now=nnow; T.qry(); } for(int o=i;o<=min(n,i+k-1);o++) for(int p=j;p<=now;p++)T.upd(a[o][p],-1); } } printf("%lld",num-ans); } signed main(){ // freopen("disinfect.in","r",stdin);freopen("disinfect.out","w",stdout); slv(); return 0; }