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;

const int N = 5010;
int f[N][N];
bool up[N][N], le[N][N];

void solve(int x, int y) {
	if (x & 1) return;
	if (y & 1) {
		up[x / 2 + 1][y / 2 + 1] = true;
	} else {
		le[x / 2 + 1][y / 2 + 1] = true;
	}
}

int n, m, k, d;

int main() {
	scanf("%d %d %d", &n, &m, &k);
	swap(n, m);
	n = (n + 1) / 2;
	m = (m + 1) / 2;
	scanf("%d", &d);
	for (int i = 1; i <= d; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		swap(x, y);
		solve(x, y);
	}
	for (int i = 1; i <= n; i++) {
		f[i][0] = f[i - 1][m];
		for (int j = 1; j <= m; j++) {
			f[i][j] = f[i][j - 1] + (up[i][j] ? 2 : 1);
			if (j >= 2) f[i][j] = min(f[i][j], f[i][j - 2] + 2 * (le[i][j] ? 2 : 1));
		}
	}
	if (k < m) {
		cout << -1 << endl;
		return 0;
	}
	k -= m;
	int t = f[n][m] - n * m;
	int ans = f[n][m];
	ans -= m;
	d = min(k, t);
	ans -= 2 * d;
	k -= d;
	d = min(ans, k);
	ans -= d;
	cout << ans << endl;
	return 0;
}