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 <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <complex>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define REP(i, n) for(int i=0;i<(int)n;i++)
#define REPS(i, n) for(int i=1;i<=(int)n;i++)
#define RREP(i, n) for(int i=n-1;i>=0;i--)
#define RREPS(i, n) for(int i=n;i>0;i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define pb push_back
#define eb emplace_back
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, m, q;

int check(const vector<vi> &req, const vector<vi> &rest, vi ave, int debug = 0){
	vi target;
	REP(i, n) if(accumulate(ALL(rest[i]), 0)) target.pb(i);
	random_shuffle(ALL(target));
	while(1){
		int update = false;
		REP(ii, target.size()){
			int i = target[ii];
			int ok = 1;
			REP(j, m)if(ave[j] < rest[i][j]){
				ok = 0;
				break;
			}
			if(ok){
				REP(j, m) ave[j] += req[i][j] - rest[i][j];
				swap(target[ii], target.back());
				target.pop_back();
				ii --;
				update = 1;
			}
		}
		if(!update) break;
	}
	return target.empty();
}

int main(){
	scanf("%d%d%d", &n, &m, &q);
	vi res(m);
	vector<vi> req(n, vi(m));
	REP(i, m) scanf("%d", &res[i]);
	REP(i, n)REP(j, m) scanf("%d", &req[i][j]);
	vector<pii> query;
	REP(i, q){
		int a, b;
		scanf("%d%d", &a, &b);a --; b --;
		query.eb(a, b);
	}
	int l = 0, r = q+1; // [0, l): ok, [0, r): NG
	
	vi checking(m);
	iota(ALL(checking), 0);
	random_shuffle(ALL(checking));

	while(l+1<r){
		int mid = (l+r)/2;
		auto rest = req;
		auto ave = res;
		REP(i, mid){
			int a, b;
			tie(a, b) = query[i];
			rest[a][b] --;
			ave[b] --;
			int f = 1;
			for(int j : checking){
				if(rest[a][j]){
					f = 0;
					break;
				}
			}
			if(f){
				for(int j : checking) ave[j] += req[a][j];
			}
		}
		if(check(req, rest, ave)) l = mid;
		else r = mid;
	}
	if(l == q) cout << -1 << endl;
	else cout << r << endl;
	return 0;
}