[HOJ] 244 - Garden

#include<stdio.h>
#include<string.h>
#define INF 99999999
#define area(a,b,c,d) (add[b][d]-add[a-1][d]-add[b][c-1]+add[a-1][c-1])
int s[250][250]={0},add[250][250]={0},Sl[250]={},Sr[250]={0},p,k,n,m;
void cnt1(){
    int i,j,A=INF,h,L,R,w;
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            A=INF;
            for(L=R=1;R<=m;){
                w=R;
                h=area(i,j,L,R);
                if(h==k && (R-L+1+j-i+1)*2<A) A=(R-L+1+j-i+1)*2;
                if(h==k && L!=R) L++;
                else if(h==k && L==R) R++;
                if(h>k) L++;
                if(h<k) R++;
                if(!Sl[w] || A<Sl[w]) Sl[w]=A;

            }
        }
    }
    A=INF;
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            A=INF;
            for(L=R=m;L>0;){
                w=L;
                h=area(i,j,L,R);
                if(h==k && (R-L+1+j-i+1)*2<A) A=(R-L+1+j-i+1)*2;
                if(h==k && L!=R) R--;
                else if(h==k && L==R) L--;
                if(h>k) R--;
                if(h<k)  L--;
                if(!Sr[w] || A<Sr[w]) Sr[w]=A;
            }
        }
    }
}
void cnt2(){
    int i,j,A=INF,h,L,R,w,d;
    for(i=1;i<=m;i++){
        for(j=i;j<=m;j++){
            A=INF;
            for(L=R=1;R<=n;){
                w=R;
                h=area(L,R,i,j);
                if(h==k && (R-L+1+j-i+1)*2<A) A=(R-L+1+j-i+1)*2;
                if(h==k && L!=R) L++;
                else if(h==k && L==R) R++;
                if(h>k) L++;
                if(h<k) R++;
                if(!Sl[w] || A<Sl[w]) Sl[w]=A;
            }
        }
    }
    A=INF;
    for(i=1;i<=m;i++){
        for(j=i;j<=m;j++){
            A=INF;
            for(L=R=n;L>0;){
                w=L,d=R;
                h=area(L,R,i,j);
                if(h==k && (R-L+1+j-i+1)*2<A) A=(R-L+1+j-i+1)*2;
                if(h==k && L!=R) R--;
                else if(h==k && L==R) L--;
                if(h>k) R--;
                if(h<k)  L--;
                if(!Sr[w] || A<Sr[w]) Sr[w]=A;
            }
        }
    }
}
int main(){
    //freopen("gar19b.in","r",stdin);
    int x,y,i,j,ans=INF;
    scanf("%d%d%d%d",&n,&m,&p,&k);
    for(i=0;i<p;i++){
        scanf("%d%d",&x,&y);
        s[x][y]++;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            add[i][j]=add[i-1][j]+add[i][j-1]-add[i-1][j-1]+s[i][j];
    cnt1();
    for(i=1;i<m;i++){
        if(Sl[i]+Sr[i+1]<ans) ans=Sl[i]+Sr[i+1];
    }
    /*for(i=1;i<=n;i++)
        printf("%d.",Sr[i]);*/
    memset(Sr,0,sizeof(Sr));
    memset(Sl,0,sizeof(Sl));
    cnt2();
    for(i=1;i<n;i++){
        if(Sl[i]+Sr[i+1]<ans) ans=Sl[i]+Sr[i+1];
    }
    if(ans==INF) puts("NO");
    else printf("%d\n",ans);
}