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 <vector>
#include <algorithm>
using namespace std;
int p,r,T;
int N[300][300];
vector<int> L,P,R;

bool isAvoidable(int t){
    int H[p][r];
    fill(H[0],H[p],0);
    vector<int> LL=L;
    for(int i=0;i<t;i++){
        H[P[i]][R[i]]++;
        LL[R[i]]--;
    }
    vector<int> satisfied(p);
    for(int i=0;i<p;i++){
        satisfied[i]=true;
        for(int j=0;j<r;j++){
            if(N[i][j]!=H[i][j]){
                satisfied[i]=false;
                break;
            }
        }
        if(satisfied[i]){
            for(int j=0;j<r;j++){
                LL[j]+=H[i][j];
            }
        }
    }
    bool updated=true;
    while(updated){
        updated=false;
        for(int i=0;i<p;i++){
            if(satisfied[i]) continue;
            bool satisfiable=true;
            for(int j=0;j<r;j++){
                if(H[i][j]+LL[j]<N[i][j]){
                    satisfiable=false;
                    break;
                }
            }
            if(satisfiable){
                satisfied[i]=true;
                for(int j=0;j<r;j++){
                    LL[j]+=H[i][j];
                }
                updated=true;
            }
        }
    }
    bool ret = true;
    for(int i=0;i<p;i++){
        if(!satisfied[i]){
            ret=false;
            break;
        }
    }
    return ret;
}

int main(){
    cin>>p>>r>>T;
    L.resize(r);
    for(int i=0;i<r;i++) cin>>L[i];
    for(int i=0;i<p;i++){
        for(int j=0;j<r;j++){
            cin>>N[i][j];
        }
    }
    P.resize(T); R.resize(T);
    for(int i=0;i<T;i++){
        cin>>P[i]>>R[i];
        P[i]--; R[i]--;
    }
    if(!isAvoidable(0)){
        cout<<0<<endl;
        return 0;
    }
    if(isAvoidable(T)){
        cout<<-1<<endl;
        return 0;
    }
    int lo=0,up=T;
    while(up-lo>=2){
        int mid = (lo+up)/2;
        if(isAvoidable(mid)){
            lo=mid;
        }else{
            up=mid;
        }
    }
    cout<<up<<endl;

    return 0;
}