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;
    for (int i = 1; i <= p; ++i) {
        int mark = 0;
        for (int j = 1; j <= r; ++j)
            if (grid[i][j] < ned[i][j]) {
                mark = 1;
                break;
            }
        if (mark == 0) {
            bo[i] = 1;
            ++tot;
            for (int j = 1; j <= r; ++j)
                used[j] -= grid[i][j];
        }
    }
    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] + num[j] - used[j] < ned[i][j]) {
                        mark = 1;
                        break;
                    }
                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;
}