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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <utility>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define rep(i,n) for (int i=0;i<n;++i)
#define REP(i,n) for (int i=1;i<=n;++i)
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define pf push_front
#define F first
#define S second
#define read(x) scanf("%d",&x)
int P,R,T;
int pp[305][305];
int rr[305];
class state{
public:
	int p[305][305];
	int r[305];
	inline bool off(int i){
		for (int j=1;j<=R;++j) if (p[i][j]) return 0;
		return 1;
	}
	inline bool on(int i){
		for (int j=1;j<=R;++j) if (p[i][j]) return 1;
		return 0;
	}
	inline bool available(int i){
		for (int j=1;j<=R;++j) if (p[i][j]>r[j]) return 0;
		return 1;
	}
	inline void release(int i){
		for (int j=1;j<=R;++j) r[j]+=pp[i][j];
	}
	inline bool judge(){// O(n^3)
		int p1[305][305],r1[305];
		rep(i,305) rep(j,305) p1[i][j]=p[i][j];
		rep(j,305) r1[j]=r[j];
		while(1){
			int cnt=0;
			for (int i=1;i<=P;++i) if (on(i)) ++cnt;
			if (!cnt){
				rep(i,305) rep(j,305) p[i][j]=p1[i][j];
				rep(j,305) r[j]=r1[j];
				return 1;
			}
			bool term=1;
			for (int i=1;i<=P;++i){
				if (off(i)) continue;
				if (available(i)){
					term=0;
					for (int j=1;j<=R;++j){
						r[j]-=p[i][j];p[i][j]=0;r[j]+=pp[i][j];
					}
					break;
				}
			}
			if (term){
				rep(i,305) rep(j,305) p[i][j]=p1[i][j];
				rep(j,305) r[j]=r1[j];
				return 0;
			}
		}
		
	}
	state operator = (const state& st){
		rep(i,305) rep(j,305) p[i][j]=st.p[i][j];
		rep(j,305) r[j]=st.r[j];
		return *this;
	}
};

int p_[200005],r_[200005];
map<int,state> m;
map<int,state>::iterator it;
int main(){
	std::ios::sync_with_stdio(false);
	cin>>P>>R>>T;
	for (int i=1;i<=R;++i){
		cin>>rr[i];m[0].r[i]=rr[i];
	}
	for (int i=1;i<=P;++i) for (int j=1;j<=R;++j){
		cin>>pp[i][j];m[0].p[i][j]=pp[i][j];
	}
	m[T]=m[0];
	for (int i=1;i<=T;++i){
		cin>>p_[i]>>r_[i];
		--m[T].p[p_[i]][r_[i]];
		--m[T].r[r_[i]];
	}
	for (int i=1;i<=P;++i) if (m[0].on(i)&&m[T].off(i)) m[T].release(i);
	if (m[T].judge()){
		cout<<-1<<endl;return 0;
	}
	if (!m[0].judge()){
		cout<<0<<endl;return 0;
	}
	int l=0,r=T;// l can, r can't
	while(r-l>1){
		int t=(l+r)/2;
		m[t]=m[l];
		for (int i=l+1;i<=t;++i){
			--m[t].p[p_[i]][r_[i]];
			--m[t].r[r_[i]];
		}
		for (int i=1;i<=P;++i) if (m[l].on(i)&&m[t].off(i)) m[t].release(i);
		if (m[t].judge()) l=t;
		else r=t;
	}
	cout<<r<<endl;
	return 0;
}