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;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int p, r, t;
	cin >> p >> r >> t;
	vi resource(r);
	REP(i, r) cin >> resource[i];
	vector<vi> need(p, vi(r));
	REP(i, p)REP(j, r) cin >> need[i][j];
	vector<pii> query;
	REP(i, t)
	{
		int a, b; cin >> a >> b;
		a--; b--;
		query.emplace_back(a, b);
	}		

	int lb = 0, ub =  t + 1;
	while (ub - lb > 1)
	{
		int time = (ub + lb) / 2;
		auto available = resource;
		auto tmp = need;
		REP(i, time)
		{
			int p = query[i].first, r = query[i].second;
			available[r]--;
			tmp[p][r]--;
		}
		vector<bool> f(p, true);
		REP(i, p)
		{
			bool ff = true;
			REP(j, r)
			{
				if (tmp[i][j] > 0) ff = false;
			}
			if (ff)
			{
				f[i] = false;
				REP(j, r) available[j] += need[i][j];
			}
		}
		bool update = true;
		while (update)
		{
			update = false;
			REP(i, p)
			{
				if (!f[i]) continue;
				bool ff = true;
				REP(j, tmp[i].size())
				{
					if (tmp[i][j] > available[j])
					{
						ff = false;
					}
				}
				if (ff)
				{
					REP(j, r) available[j] += need[i][j] - tmp[i][j];
					update = true;
					f[i] = false;
				}
			}
		}
		bool ok = true;
		REP(i, p)
		{
			if (f[i]) ok = false;
		}
		if (ok) lb = time;
		else ub = time;
	}
	if (ub == t + 1) cout << -1 << endl;
	else cout << ub << endl;
	return 0;
}