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:
#pragma GCC optimize "O3"
#include<bits/stdc++.h>

using namespace std;

constexpr int N = 1e5 + 1;

int w, h, k, n, dp[N];
vector<vector<bool>> dogs;

int main() {
  scanf("%d %d %d %d", &w, &h, &k, &n); --h, --w;
  if(k < (w+2)/2) {
    puts("-1");
    return 0;
  }
  k -= (w+2) / 2;
  dogs.resize(h+1, vector<bool>(w+1));
  for(int i = 0; i < n; ++i) {
    int x, y; scanf("%d %d", &x, &y); --x, --y;
    dogs[y][x] = true;
  }
  int ans = 0, bad = 0;
  for(int i = 2; i <= h; i += 2) {
    fill(dp, dp+w+1, 0);
    dp[0] = dogs[i-1][0] + 1;
    if(w >= 2)
      dp[2] = min(dp[0] + dogs[i-1][2] + 1, (dogs[i-1][1] + 1) * 2);
    for(int j = 4; j <= w; j += 2)
      dp[j] = min(dp[j-2] + dogs[i-1][j] + 1,
                  dp[j-4] + (dogs[i-1][j-1] + 1) * 2);
    bad += (dp[w] - ((w+2) / 2));
    ans += dp[w];
  }
  printf("%d\n", max(0, ans - k - min(k, bad)));
}