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>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,r,t;
int l[301];
int p[200001],req[200001];
int fie[301][301];
int tmpf[301][301];
int tmpl[301];
int cnt[301];
bool used[301];

bool C(int vt){
	memset(used,0,sizeof(used));
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<r;i++){
		tmpl[i]=l[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<r;j++){
			tmpf[i][j]=0;
			if(tmpf[i][j]==fie[i][j])cnt[i]++;
		}
	}
	for(int i=0;i<n;i++){
		if(cnt[i]==r){
			used[i]=true;
		}
	}
	int restcnt=n;
	for(int i=0;i<vt;i++){
		if(tmpl[req[i]]==0)continue;
		tmpf[p[i]][req[i]]++;
		tmpl[req[i]]--;
		if(tmpf[p[i]][req[i]]==fie[p[i]][req[i]])cnt[p[i]]++;
		if(cnt[p[i]]==r){
			used[p[i]]=true;
			restcnt--;
			for(int j=0;j<r;j++){
				tmpl[j]+=tmpf[p[i]][j];
			}
		}
	}
	bool update=true;
	while(update){
		update=false;
		for(int i=0;i<n;i++){
			if(!used[i]){
				bool flag=true;
				for(int j=0;j<r;j++){
					if(fie[i][j]-tmpf[i][j]>tmpl[j])flag=false;
				}
				if(flag){
					used[i]=true;
					update=true;
					restcnt--;
					for(int j=0;j<r;j++){
						tmpl[j]+=tmpf[i][j];
					}
				}
			}
		}
	}
	return (restcnt>0);
}

int main(void){
	scanf("%d%d%d",&n,&r,&t);
	for(int i=0;i<r;i++){
		scanf("%d",&l[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<r;j++){
			scanf("%d",&fie[i][j]);
		}
	}
	for(int i=0;i<t;i++){
		scanf("%d%d",&p[i],&req[i]);
		p[i]--;
		req[i]--;
	}
	int l=0,r=t+1;
	while(l+1<r){
		int mid=(l+r)/2;
		if(C(mid))r=mid;
		else l=mid;
	}
	printf("%d\n",r==(t+1)?-1:r);
	return 0;
}