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;
// #define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cout<<(#v)<<":";for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1e9;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

int cost[10000][10000];
int dp[10000];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int W, H, K, N;
    cin >> W >> H >> K >> N;
    rep(i, H) rep(j, W) cost[i][j] = 1;
    rep(i, N) {
        int c, r;
        cin >> c >> r;
        c--; r--;
        cost[r][c] = 2;
    }

    if (K < (W + 1) / 2) {
        cout << -1 << endl;
        return 0;
    }

    if (H == 1) {
        cout << 0 << endl;
        return 0;
    }

    int n1 = 0, n2 = 0;
    for (int i = 2; i < H; i += 2) {
        dp[0] = cost[i - 1][0];
        if (W >= 3) dp[2] = min(dp[0] + cost[i - 1][2], 2 * cost[i - 1][1]);
        for (int j = 4; j < W; j += 2) {
            dp[j] = min(dp[j - 2] + cost[i - 1][j], dp[j - 4] + 2 * cost[i - 1][j - 1]);
        }
        int t2 = dp[W - 1] - (W + 1) / 2;
        int t1 = (W + 1) / 2 - t2;
        n1 += t1;
        n2 += t2;
    }

    int r = K - (W + 1) / 2;
    int t = min(r, n2);
    n2 -= t;
    r -= t;
    int u = min(r, n1);
    n1 -= u;
    r -= u;

    cout << 1 * n1 + 2 * n2 << endl;

}