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 <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
void print();
int n,m,k;
int alloc_data[305];
int need_data[305][305];
pii data[200005];
int alloc[305];
int need[305][305];
int zero[305];
bool use[305];

inline void recover(int x)
{
	use[x]=false;
	zero[x]=0;
	for(int i=0;i<m;i++)
	{
		alloc[i]+=need_data[x][i]-need[x][i];
		need[x][i]=need_data[x][i];
		zero[x]+=(need[x][i]==0);
	}
}

inline void run(int x)
{
	memset(use,false,sizeof(use));
	for(int i=0;i<n;i++)
	{
		alloc[i]=alloc_data[i];
	}
	for(int i=0;i<n;i++)
	{
		zero[i]=0;
		for(int j=0;j<m;j++)
		{
			need[i][j]=need_data[i][j];
			zero[i]+=(need_data[i][j]==0);
		}
	}
	for(int i=0;i<=x;i++)
	{
		use[data[i].first]=true;
		alloc[data[i].second]--;
		need[data[i].first][data[i].second]--;
		if(need[data[i].first][data[i].second]==0) zero[data[i].first]++;
		if(zero[data[i].first]==m) recover(data[i].first);
	}
}

inline bool check(int x)
{
	run(x);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(use[j]==false) continue;
			bool flag=true;
			for(int k=0;k<m;k++)
			{
				if(alloc[k]<need[j][k])
				{
					flag=false;
					break;
				}
			}
			if(flag==true) recover(j);
		}
	}
	for(int i=0;i<n;i++)
	{
		if(use[i]) return true;
	}
	return false;
}

void print()
{
	cout<<"ÄÚ´æÊ¹ÓÃÇé¿ö£º\n";
	for(int i=0;i<m;i++)
	{
		cout<<alloc[i]<<' ';
	}
	cout<<endl;
}

int main()
{
//	freopen("input.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin>>n>>m>>k;
	for(int i=0;i<m;i++)
	{
		cin>>alloc_data[i];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>need_data[i][j];
		}
	}
	for(int i=0;i<k;i++)
	{
		cin>>data[i].first>>data[i].second;
		data[i].first--;
		data[i].second--;
	}
	int l=0,r=k-1,res=-2,mid;
	while(l<=r)
	{
		mid=l+((r-l)>>1);
		if(check(mid))
		{
			res=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<res+1<<endl;
	return 0;
}