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 <iostream>
#define inf 2e9

using namespace std;

int w, h, k, n;
int dog[5005][10005];
int dp[5005][2];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> w >> h >> k;
	cin >> n;
	int x, y;
	for(int i = 1; i <= n; i++){
		cin >> x >> y;
		if(y%2) continue;
		dog[y/2][x] = 1;
	}
	if(w%2 == 0) w--;
	if(h%2 == 0) h--;
	int W = w/2+1;
	
	k -= W;
	if(k < 0){
		cout << -1 << endl;
		return 0;
	}
	
	int ans = 0;
	for(int i = 1; i <= h/2; i++){
		dp[0][0] = 0, dp[0][1] = inf;
		for(int j = 1; j <= W; j++){
			dp[j][0] = min(dp[j-1][0] + dog[i][j*2-1], dp[j-1][1] + dog[i][j*2-2]);
			if(j < W) dp[j][1] = dp[j-1][0] + dog[i][j*2];
		}
		ans += dp[W][0];
	}
	
	int base = h/2*W - ans;
	if(ans < k) k -= ans, ans = 0;
	else ans -= k, k = 0;
	cout << ans*2 + max(base - k, 0) << endl;
	
	return 0;
}