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:
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
inline string getstr(string &s,int l,int r){string ret="";for(int i=l;i<=r;i++)ret.push_back(s[i]);return ret;}
int modpow(int x,int y,int md=mod){if(y==0)return 1;int ret=modpow(x,y>>1,md);ret=(ll)ret*ret%md;if(y&1)ret=(ll)ret*x%md;return ret;}
int n,m,t;
int have[303],dat[303];
int need[303][303];
int now[303][303];
int a[200005],b[200005];
inline bool ok(int step){
	memset(now,0,sizeof now);
	memcpy(have,dat,sizeof have);
	for(int i=1;i<=step;i++){
		now[a[i]][b[i]]++;
		have[b[i]]--;
	}
	for(int i=1;i<=n;i++){
		int mul=inf;
		for(int j=1;j<=m;j++)if(need[i][j])mul=min(mul,now[i][j]/need[i][j]);
		for(int j=1;j<=m;j++)have[j]+=mul*need[i][j],now[i][j]-=mul*need[i][j];
	}
	while(1){
		bool change=false;
		for(int i=1;i<=n;i++){
			if(*max_element(now[i],now[i+1])==0)continue;
			bool ok=true;
			for(int j=1;j<=m;j++)if(need[i][j]-now[i][j]>have[j])ok=false;
			if(ok){
				for(int j=1;j<=m;j++)have[j]+=now[i][j],now[i][j]=0;
				change=true;
			}
		}
		if(!change)break;
	}
	if(*max_element(now[1],now[n+1])>0)return false;
	return true;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>t;
	for(int i=1;i<=m;i++)cin>>dat[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>need[i][j];
		}
	}
	for(int i=1;i<=t;i++)cin>>a[i]>>b[i];
	int l=0,r=t+1;
	while(r-l>1){
		int mid=l+r>>1;
		if(ok(mid))l=mid;
		else r=mid;
	}
	cout<<(r==t+1?-1:r)<<endl;
	return 0;
}