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:
/*-------------------*/
/*       Darsein     */
/*      O(K logK)    */
/* implement: 40 min */
/* debug:     20 min */
/*-------------------*/

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

int main(){
  long long w,h,k,n;
  cin >> w >> h >> k >> n;

  map< int, vector<int> > odd, even;
  set<int> row;
  for(int i=0;i<n;i++){
    int x,y;
    cin >> x >> y;
    if(x&1) odd[y].emplace_back(x);
    else even[y].emplace_back(x);
    row.emplace(y);
  }

  if((w+1)/2 > k){
    cout << -1 << endl;
    return 0;
  }
  k -= (w+1)/2;

  long long ans = 0;
  for(auto r : row){
    vector<int> e = even[r];
    e.emplace_back(0);
    e.emplace_back(w+1);
    sort(e.begin(), e.end());

    vector<int> o = odd[r];
    sort(o.begin(), o.end());
    size_t oidx = 0;

    for(size_t i=1;i<e.size();i++){
      int len = (e[i] - e[i-1])/2;
      if(len%2 == 0) continue;

      int cnt = 0;
      while(oidx < o.size() && o[oidx] < e[i-1]) oidx++;
      while(oidx < o.size() && o[oidx] < e[i]){
	int relative_pos = (o[oidx] - e[i-1])/2;
	if(relative_pos%2==0) cnt++;
	oidx++;
      }
      if(cnt == (len+1)/2) ans++; 
    }
  }

  ans = max(0LL, ans-k);
  cout << max(0LL, (h-1)/2*(w+1)/2 + ans - k) << endl;
}