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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 10001

int H,W,num_special,num_dog;
bool exist_dog[NUM];
vector<int> ODD[NUM],EVEN[NUM];


int main(){

	scanf("%d %d %d %d",&W,&H,&num_special,&num_dog);

	for(int row = 2; row <= H-1; row += 2)exist_dog[row] = false;

	int tmp_col,tmp_row;
	for(int loop = 0; loop < num_dog; loop++){

		scanf("%d %d",&tmp_col,&tmp_row);

		if(tmp_row%2 == 1)continue;

		if(tmp_col%2 == 1){

			ODD[tmp_row].push_back(tmp_col);

		}else{
			EVEN[tmp_row].push_back(tmp_col);
		}
		exist_dog[tmp_row] = true;
	}

	if(num_special < (W+1)/2){
		printf("-1\n");
		return 0;
	}

	num_special -= (W+1)/2;
	int num_cost_1 = ((H-1)/2)*((W+1)/2);
	int num_cost_2 = 0;
	int num_house,index,num_odd_order_dog;

	for(int row = 2; row <= H-1; row += 2){

		if(!exist_dog[row])continue;
		sort(ODD[row].begin(),ODD[row].end());

		EVEN[row].push_back(0);
		EVEN[row].push_back(W+1);
		sort(EVEN[row].begin(),EVEN[row].end());

		index = 0;

		for(int i = 1; i < EVEN[row].size(); i++){

			num_house = (EVEN[row][i]-EVEN[row][i-1])/2;
			if(num_house%2 == 0)continue;

			num_odd_order_dog = 0;

			while(index < ODD[row].size() && ODD[row][index] < EVEN[row][i-1])index++;
			while(index < ODD[row].size() && ODD[row][index] < EVEN[row][i]){

				if(((ODD[row][index]-EVEN[row][i-1])/2)%2 == 0){
					num_odd_order_dog++;
				}
				index++;
			}
			if(num_odd_order_dog == (num_house+1)/2)num_cost_2++;
		}
	}
	num_cost_1 -= num_cost_2;

	if(num_cost_2 < num_special){

		num_special -= num_cost_2;
		num_cost_2 = 0;
		num_cost_1 = max(0,num_cost_1-num_special);

	}else{

		num_cost_2 -= num_special;
	}

	printf("%d\n",num_cost_1+2*num_cost_2);

	return 0;
}