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:
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

int main(){
    iostream_init();
    int P, R, K;
    while(cin >> P >> R >> K) {
        vector<int> all(R);
        vector<vector<int>> need_(P, vector<int>(R, 0));

        REP(i, R) cin >> all[i];
        REP(i, P) REP(j, R) cin >> need_[i][j];

        vector<int> X(K);
        vector<int> Y(K);
        REP(i, K) cin >> X[i] >> Y[i];
        REP(i, K) X[i]--;
        REP(i, K) Y[i]--;

        auto zero = [&]() {
            REP(i, P) {
                REP(j, R) if(need_[i][j] > all[j]) return true;
            }
            return false;
        };
        assert(!zero());

        auto check = [&](int T) {
            vector<int> cur = all;
            vector<vector<int>> need = need_;
            vector<vector<int>> take(P, vector<int>(R, 0));
            vector<int> have(P);
            vector<int> rest(P);
            REP(i, P) REP(j, R) rest[i] += need[i][j];

            REP(i, T) {
                cur[ Y[i] ]--;
                need[ X[i] ][ Y[i] ]--;
                take[ X[i] ][ Y[i] ]++;
                have[ X[i] ]++;
                if(--rest[X[i]] == 0) {
                    have[X[i]] = 0;
                    REP(j, R) {
                        cur[j] += take[ X[i] ][j];
                    }
                }
            }

            while(true) {
                bool updated = false;
                REP(i, P) if(have[i] > 0) {
                    bool ok = true;
                    REP(j, R) if(need[i][j] > cur[j]){ ok = false; break; }
                    if(ok) {
                        updated = true;
                        have[i] = 0;
                        REP(j, R) cur[j] += take[i][j];
                    }
                }
                if(!updated) break;
            }

            REP(i, P) if(have[i]) return false;
            return true;
        };

        if(check(K)) {
            cout << -1 << endl;
            continue;
        }

        int lb = 0, ub = K + 1;
        // [lb, ub)
        while(ub - lb > 1) {
            int T = (lb + ub) / 2;
            if(check(T)) {
                lb = T;
            } else {
                ub = T;
            }
        }

        assert(lb != K);

        cout << ub << endl;
    }
    return 0;
}