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 <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <iostream> 
using namespace std;
 
pair<int, int> P[200005];
 
int p, r, t;
 
int ned[305][305];
int num[305];
 
int grid[305][305];
int used[305];
int bo[305];
 
int check(int t) {
    memset(used, 0, sizeof(used));
    memset(grid, 0, sizeof(grid));
    memset(bo, 0, sizeof(bo));
    for (int i = 1; i <= t; ++i) {
        ++used[P[i].second];
        ++grid[P[i].first][P[i].second];
    }
    int tot = 0;
    while (1) {
        int flag = 0;
        for (int i = 1; i <= p; ++i)
            if (!bo[i]) {
                int mark = 0;
                for (int j = 1; j <= r; ++j)
                    if (grid[i][j] + max(num[j] - used[j], 0) < ned[i][j])
                        mark = 1;
                if (mark == 0) {
                    flag = i;
                    break;
                }
            }
        if (flag == 0) break;
        bo[flag] = 1;
        ++tot;
        for (int j = 1; j <= r; ++j)
            used[j] -= grid[flag][j];
    }
    return tot == p;
}
 
int main() {
    scanf("%d%d%d", &p, &r, &t);
    for (int i = 1; i <= r; ++i) {
        scanf("%d", &num[i]);
    }
    for (int i = 1; i <= p; ++i)
        for (int j = 1; j <= r; ++j)
            scanf("%d", &ned[i][j]);
    for (int i = 1; i <= t; ++i) {
        scanf("%d%d", &P[i].first, &P[i].second);
    }
    // cout << check(0) << endl;
    if (check(t)) {
        puts("-1");
    }
    else {
        int head = 0, tail = t;
        while (head < tail - 1) {
            int mid = (head + tail) >> 1;
            if (check(mid)) head = mid;
            else tail = mid;
        }
        cout << tail << endl;
    }
    return 0;
}