Problem: Example

Input

2 2 7
3 4
3 2
1 3
1 1
2 2
1 2
2 1
1 2
2 2
1 1


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, r, t;
int res[300];
int need[300][300];
int R[200000];
int P[200000];
typedef pair<int, int> Pii;

bool check(int x){
	int sum[300][300] = { 0 };
	int rem[300] = { 0 };
	memcpy(rem, res, sizeof res);

	for(int i = 0; i < x; i++){
		//if(rem[R[i]] == 0) return false;
		rem[R[i]]--;
		sum[P[i]][R[i]]++;
	}
	int fin[300] = { 0 };
	for(int i = 0; i < N; i++){
		int cnt = 0;
		for(int j = 0; j < r; j++){
			if(sum[i][j] == need[i][j]) cnt++;
		}
		if(cnt == r){
			fin[i] = 1;
			for(int j = 0; j < r; j++){
				rem[j] += sum[i][j];
			}
		}
	}
	while(true){
		bool update = false;
		for(int i = 0; i < N; i++){
			if(fin[i]) continue;
			int cnt = 0;
			for(int j = 0; j < r; j++){
				int c = need[i][j] - sum[i][j];
				if(c <= rem[j]) cnt++;
			}
			if(cnt == r){
				fin[i] = 1;
				for(int j = 0; j < r; j++){
					rem[j] += sum[i][j];
				}
				update = true;
			}
		}
		if(!update) break;
	}
	for(int i = 0; i < N; i++){
		if(fin[i] == 0) return false;
	}
	return true;
}


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	while(cin >> N >> r >> t){
		for(int i = 0; i < r; i++){
			cin >> res[i];
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < r; j++){
				cin >> need[i][j];
			}
		}
		for(int i = 0; i < t; i++){
			cin >> P[i] >> R[i];
			P[i]--, R[i]--;
		}

		if(check(t)){
			cout << -1 << endl;
			continue;
		}

		int ok = 0, ng = t;
		while(abs(ok - ng) > 1){
			int mid = (ok + ng) / 2;
			if(check(mid)) ok = mid;
			else ng = mid;
		}

		cout << ng << endl;
	}
}