p0TjKk - Online C++ Compiler & Debugging Tool

#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=5050;
const int R=3030;

int r,c,n,k,prv[N],nxt[N],vy[N];
ii pt[N];
vector<int> pos[R];
bool on[N];

inline int c2(int x){
    if(x<0) return 0;
    return x*(x-1)/2 + x;
}

void solve(){
    cin>>r>>c>>n>>k;

    if(k==0){
        /// do something
        cout<<1LL*c2(r)*c2(c)<<'\n';
        return;
    } else{
        --k;
    }

    foru(i,1,n){
        int x,y; cin>>x>>y;
        pt[i]={x,y};
    }

    sort(pt+1, pt+1+n, [](ii x, ii y){return x.se<y.se;});
    foru(i,1,n){
        int x=pt[i].fi, y=pt[i].se;
        vy[i]=y;
        pos[x].eb(i);
    }
    vy[0]=0; vy[n+1]=c+1;

    ll ans=0;
    foru(i,1,r){
        foru(j,i,r){
            for(int id:pos[j]){
                on[id]=1;
            }
        }

        int lst=0;
        foru(j,1,n) if(on[j]){
            prv[j]=lst;
            nxt[lst]=j;
            lst=j;
        }
        nxt[lst]=n+1;

        ll cur=0;
        foru(j,1,n) if(on[j]){
            int x=j;
            foru(l,1,k){
                if(x==n+1) break;
                cur+=(vy[j]-vy[prv[j]])*(vy[nxt[x]]-vy[x]);
                x=nxt[x];
            }
            cur+=c2(vy[j]-vy[prv[j]]-1);
            if(nxt[j]==n+1) cur+=c2(vy[nxt[j]]-vy[j]-1);
        }
        if(nxt[0]==n+1) cur=c2(c);

        ford(j,r,i){
//            cout<<i<<" "<<j<<" "<<cur<<'\n';
            ans+=cur;
            for(int id:pos[j]){
                int lp=id, rp=id, cnt=k;
                foru(_,2,k+1){
                    if(prv[lp]==0) break;
                    lp=prv[lp]; --cnt;
                }
                while(cnt>0){
                    if(nxt[rp]==n+1) break;
                    rp=nxt[rp];
                    --cnt;
                }

                if(cnt==0){
                    while(lp!=id){
                        if(rp==n+1) break;
                        cur+=(vy[lp]-vy[prv[lp]])*(vy[nxt[rp]]-vy[rp]);
                        lp=nxt[lp]; rp=nxt[rp];
                    }
                    if(rp!=n+1){
                        cur+=(vy[lp]-vy[prv[lp]])*(vy[nxt[rp]]-vy[rp]);
                    }
                }

                nxt[prv[id]]=nxt[id];
                prv[nxt[id]]=prv[id];
                on[id]=false;
            }
        }
    }


//    cout<<ans<<'\n';
//    cout<<1LL*c2(r)*c2(c)<<'\n';
    cout<<1LL*c2(r)*c2(c) - ans<<'\n';
}

int32_t main(){
    #define task "recs"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int the; //cin>>the;
    int tc=1; //cin>>tc;
    rep(_,tc){
        solve();
    }
}