#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MaxN=5007; inline bool LD(int x,int y,int i,int j){ return (x<=i)&&(y<=j); } inline bool RU(int x,int y,int i,int j){ return LD(i,j,x,y); } int n,m,S; int C=0; int buc[MaxN]; int XL[MaxN],XR[MaxN],YL[MaxN],YR[MaxN]; int V=0; inline void sub50(){ int ans=1e9; for(int p=1;p<=min(n,S);p++){ int q=min(S/p,m); for(int i=1;i<=n-p+1;i++){ for(int j=1;j<=m-q+1;j++){ int i2=i+p-1; int j2=j+q-1; int t=0; for(int c=1;c<=V;c++){ if(!XR[c])continue; if(LD(i,j,XL[c],YL[c])&&RU(i2,j2,XR[c],YR[c]))t++; } ans=min(ans,C-t); } } } cout<<ans<<endl; return; } int p[MaxN]; inline void subcol(){ int ans=C; for(int T=0;T<(1<<C);T++){ int xl=1e9,xr=0,yl=1e9,yr=0; int t=0; for(int i=0;i<C;i++){ int c=p[i]; if((T>>i)&1){ ++t; xl=min(xl,XL[c]); xr=max(xr,XR[c]); yl=min(yl,YL[c]); yr=max(yr,YR[c]); } } if((xr-xl+1)*(yr-yl+1)<=S){ ans=min(ans,C-t); } } cout<<ans<<endl; return; } vector<int> A; bool cmp(int i,int j){return XR[i]<XR[j];} int t[MaxN]; inline int lb(int x){return x&(-x);} inline void Add(int x,int dt){ for(int i=x;i<=m;i+=lb(i))t[i]+=dt; } inline int Qry(int x){ int ans=0; for(int i=x;i;i-=lb(i))ans+=t[i]; return ans; } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("disinfect.in","r",stdin); freopen("disinfect.out","w",stdout); #endif memset(XL,63,sizeof(XL)); memset(YL,63,sizeof(YL)); cin>>n>>m>>S; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int c;cin>>c; buc[c]++; V=max(V,c); XL[c]=min(XL[c],i); XR[c]=max(XR[c],i); YL[c]=min(YL[c],j); YR[c]=max(YR[c],j); } } for(int i=1;i<=V;i++){ if(buc[i]>0){ p[C++]=i; A.push_back(i); } } sort(A.begin(),A.end(),cmp); if(n<=50&&m<=50){sub50();cout.flush();return 0;} if(V<=16){ subcol(); cout.flush(); return 0; } int maxcov=0; for(int i=1;i<=C;i++){ for(int j=1;j<=C;j++){ int xl=min(XL[p[i]],XL[p[j]]); int yl=min(YL[p[i]],YL[p[j]]); for(auto h:A){ if(LD(xl,yl,XL[h],YL[h])){ Add(YR[h],1); int xr=XR[h]; int LIM=min(yl-1+S/(xr-xl+1),m); if(LIM<yl)continue; maxcov=max(maxcov,Qry(LIM)); } } for(auto h:A){ if(LD(xl,yl,XL[h],YL[h]))Add(YR[h],-1); } } } cout<<C-maxcov<<endl; return 0; }