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;

int N,M,K;
int a[300];
int b[300][300];
int cnt[300];

int s[200000],t[200000];

int A[300];
int B[300][300];
bool check(int x){
  for(int i=0;i<M;i++){
    A[i]=a[i];
  }
  for(int i=0;i<N;i++){
    cnt[i]=0;
    for(int j=0;j<M;j++){
      B[i][j]=b[i][j];
      cnt[i]+=b[i][j];
    }
  }
  
  for(int i=0;i<x;i++){
    int p=s[i],q=t[i];
    A[q]--;
    if(A[q]<0)return false;
    
    B[p][q]--;
    cnt[p]--;
    if(cnt[p]==0){
      for(int j=0;j<M;j++)
        A[j]+=b[p][j];
    }
  }
  
  bool update=true;
  while(update){
    update=false;
    for(int i=0;i<N;i++){
      if(cnt[i]==0)continue;
      bool flg=true;
      for(int j=0;j<M;j++)
        if(A[j]<B[i][j])flg=false;
      if(!flg)continue;
      
      cnt[i]=0;
      for(int j=0;j<M;j++)
        A[j]+=(b[i][j]-B[i][j]);
      update=true;

    }
  }
  
  for(int i=0;i<N;i++){
    if(cnt[i]>0)return false;
    assert(cnt[i]==0);
  }
  return true;
}

int main(){
  scanf("%d %d %d",&N,&M,&K);
  for(int i=0;i<M;i++)scanf("%d",&a[i]);
  for(int i=0;i<N;i++)
    for(int j=0;j<M;j++)
      scanf("%d",&b[i][j]);

  for(int i=0;i<K;i++){
    scanf("%d %d",&s[i],&t[i]);
    s[i]--;
    t[i]--;
  }
  
  int left=0,right=K,mid;
  while(left<right){
    mid=(left+right)/2;
    if(check(mid))left=mid+1;
    else right=mid;
  }
  
  if(check(K))left=-1;
  printf("%d\n",left);
  return 0;
}