Problem: Example

Input

5 5 4
6
3 2
4 2
5 2
1 4
3 4
5 4


Output

6

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (1LL<<60);

ll H,W,K,N;
ll hh,ww;
ll y[100000],x[100000];

vector<ll> g[100005];
vector<ll> G[100005];

ll uc=0;

ll func(vector<ll> &T,vector<ll> &t,int l,int r, int Y){

  
  ll L=T[l];
  ll R=T[r-1];


  ll cnt = (R+1)/2 - (L-1+1)/2;

  ll res=-cnt;
  
  vector<ll> :: iterator it, it2;
  it =lower_bound(t.begin(),t.end(),L);
  it2=upper_bound(t.begin(),t.end(),R);
  
  map<int,int> mp;
  while(it!=it2){
    mp[*it]=1;
    it++;
  }


  vector<ll> dp(cnt+1,INF);

  int sx=L;
  if(sx%2==0)sx++;
  
  dp[0]=0;
  for(int i=0;i<cnt;i++){
    if(dp[i]==INF)continue;
    int px=sx+2*i;
    
    if(mp[px]){
      dp[i+1]=min(dp[i+1],dp[i]+2);
    }else{
      dp[i+1]=min(dp[i+1],dp[i]+1);
    }

    if(i+2<=cnt){
      if(mp[px+1]){
        dp[i+2]=min(dp[i+2],dp[i]+4);
      }else{
        dp[i+2]=min(dp[i+2],dp[i]+2);
      }
    }
  }

  res+=dp[cnt];
    
  return res;
}

ll solve(){
  
  hh=(H+1)/2;
  ww=(W+1)/2;
  if( ww > K )return -1;
  K-=ww;

  ll res = 0;
  ll excost = 0;
  
  for(int i=2;i<H;i+=2){
    res+=ww;
    
    if(G[i].empty()){
      continue;
    }

    int last=0;
    for(int j=1;j<(int)G[i].size();j++){
      if(G[i][j-1]+3<G[i][j]){
        ll val = func(G[i],g[i],last,j,i);
        res += val;
        excost += val;
        last=j;
      }
    }
    
    if(last+1<(int)G[i].size()){
      ll val = func(G[i],g[i],last,G[i].size(),i);
      res += val;
      excost += val;
    }
  }

  int cc=min(K,excost);
  res-=cc*2LL;
  K-=cc;
  
  return max(0LL,res-K);
}

int main(){
  cin>>W>>H>>K>>N;


  for(int i=1;i<=H;i++){
    G[i].push_back(1);
    G[i].push_back(W);
  }
  
  for(int i=0;i<N;i++){
    cin>>x[i]>>y[i];
    G[ y[i] ].push_back( x[i] );

    if(x[i]+2<=W)
      G[ y[i] ].push_back( x[i]+2 );
    if(x[i]-2>=1)
      G[ y[i] ].push_back( x[i]-2 );

    g[ y[i] ].push_back( x[i] );
    
  }

  for(int i=1;i<=H;i++){
    sort(g[i].begin(),g[i].end());
    sort(G[i].begin(),G[i].end());
    G[i].erase( unique(G[i].begin(),G[i].end()) , G[i].end() );
  }
  
  cout<<solve()<<endl;
  return 0;
}