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;
const int N = 305, T = 2e5 + 5;
int L[N], ava[N], need[N][N], has[N][N], a[T], b[T];
bool done[N];
int got[N];
int main() {
	int p, r, t;
	scanf("%d%d%d", &p, &r, &t);
	for (int i = 1; i <= r; ++ i) scanf("%d", &L[i]);
	for (int i = 1; i <= p; ++ i) {
		for (int j = 1; j <= r; ++ j) scanf("%d", &need[i][j]);
	}
	for (int i = 1; i <= t; ++ i) scanf("%d%d", &a[i], &b[i]);
	int l = 1, R = t, ans = -1;
	while (l <= R) {
		int mid = (l + R) / 2;
		memset(has, 0, sizeof(has));
		memset(ava, 0, sizeof(ava));
		memset(got, 0, sizeof(got));
		memset(done, 0, sizeof(done));
		for (int i = 1; i <= r; ++ i) ava[i] = L[i];
		int dones = 0;
		for (int i = 1; i <= p; ++ i) {
			for (int j = 1; j <= r; ++ j) if (need[i][j] == 0) {
				got[i] ++;
				if (got[i] == r) {
					done[i] = 1;
					dones ++;
				}
			}
		}
		for (int i = 1; i <= mid; ++ i) {
			has[a[i]][b[i]] ++;
			ava[b[i]] --;
			if (has[a[i]][b[i]] == need[a[i]][b[i]]) {
				got[a[i]] ++;
				if (got[a[i]] == r) {
					done[a[i]] = 1;
					dones ++;
					for (int j = 1; j <= r; ++ j) ava[j] += need[a[i]][j];
				}
			}
		}
		bool flag = 1;
		while (flag) {
			flag = 0;
			for (int i = 1; i <= p; ++ i) {
				if (done[i]) continue;
				bool can = 1;
				for (int j = 1; j <= r; ++ j) if (ava[j] + has[i][j] < need[i][j]) {
					can = 0;
					break;
				}
				if (can) {
					done[i] = 1;
					dones ++;
					flag = 1;
					for (int j = 1; j <= r; ++ j) ava[j] += has[i][j];
				}
			}
		}
		if (dones == p) {
			l = mid + 1;
		}
		else {
			R = mid - 1;
			ans = mid;
		}
	}
	printf("%d\n", ans);
}