#include <bits/stdc++.h> #define int ll using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define rng(i,c,n) for(int i=c;i<n;i++) #define fi first #define se second #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) ((int) a.size()) #define vec(...) vector<__VA_ARGS__> #define _4ab8goq ios::sync_with_stdio(0),cin.tie(0); typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} struct dsu{ int _n; vi si,par,leb; dsu(int n=0){ init(n); } void init(int n=0){ _n=n; par=vi(_n,0); si=vi(_n,0); leb=vi(_n,-1); rep(i,n){ si[i]=1; par[i]=i; } } int parent(int u){return par[u]=(par[u]==u?u:parent(par[u]));} bool same(int u,int v){return parent(u)==parent(v);} void merge(int u,int v){ u=parent(u),v=parent(v); if(!same(u,v)){ if(si[u]<si[v]) swap(u,v); leb[u]=max(leb[u],leb[v]); _n-=1; si[u]+=si[v]; par[v]=u; } } int size(int v=-1){return v==-1?_n:si[parent(v)];} }; void slv(){ int h,w,n,d; cin>>h>>w>>n>>d; vec(pii) a(n); rep(i,n){ cin>>a[i].fi>>a[i].se; } rep(i,n){ a[i].fi-=1,a[i].se-=1; } vi qs(h*w,-1); rep(i,n){ qs[a[i].fi*w+a[i].se]=i; } auto ok=[&](int i,int j){ return min(i,j)>=0 and i<h and j<w; }; dsu uf(n); rep(i,n){ auto [x,y]=a[i]; rng(di,-d,d+1){ rng(dj,-d,d+1){ if(abs(di)+abs(dj)>d) continue; int nx=x+di,ny=y+dj; if(ok(nx,ny) and qs[nx*w+ny]!=-1){ uf.merge(i,qs[nx*w+ny]); } } } } int cnt=0; rep(i,n){ if(uf.parent(i)==i){ if(uf.size(i)>1){ cnt+=1; } } } int mi=1e9,ma=0; rep(i,h){ rep(j,w){ int x=i,y=j; vi evs; rng(di,-d,d+1){ rng(dj,-d,d+1){ if(abs(di)+abs(dj)>d) continue; int nx=x+di,ny=y+dj; if(ok(nx,ny) and qs[nx*w+ny]!=-1){ // st.insert(uf.parent(mp[nx*w+ny])); evs.pb(uf.parent(qs[nx*w+ny])); } } } sort(all(evs)); evs.erase(unique(all(evs)),evs.end()); int now=cnt,e=0; for(auto v:evs){ if(uf.size(v)>1){ e+=1; } } // if(i==3 and j==2) print(sz(st),e); if(!e){ now+=(sz(evs)>0); }else{ now-=(e-1); } mi=min(mi,now); ma=max(ma,now); } } cout<<mi<<" "<<ma<<"\n"; } signed main(){ _4ab8goq; slv(); }