#include "robots.h"

#include <bits/stdc++.h>

// #define assert(exp) \
//     if (!(exp)) {   \
//         exit(0);    \
//     }

struct Flow {
    struct Edge {
        int to, id;
        int fl, cp;
    };

    int n, S, T;
    std::vector<std::vector<Edge>> gr;
    std::vector<int> dist, used;
    std::vector<int> dg;
    int flow;

    void pre_add_edge(int u, int v, int cp) {
        dg[u]++;
        dg[v]++;
        // int a = gr[u].size();
        // int b = gr[v].size();
        // gr[u].push_back(Edge{v, b, 0, cp});
        // gr[v].push_back(Edge{u, a, cp, cp});
    }

    void init_gr() {
        for (int i = 0; i < n; i++) {
            gr[i].reserve(dg[i]);
        }
    }

    void add_edge(int u, int v, int cp) {
        int a = gr[u].size();
        int b = gr[v].size();
        gr[u].push_back(Edge{v, b, 0, cp});
        gr[v].push_back(Edge{u, a, cp, cp});
    }

    Flow(int n, int S = 0, int T = 1) : n(n), S(S), T(T), gr(n), dist(n), used(n), flow(0), dg(n) {
        ;
    }

    void bfs(int f) {
        dist.assign(n, n);
        std::deque<int> deque;
        deque.push_back(f);
        dist[f] = 0;
        while (deque.size()) {
            int v = deque.front();
            deque.pop_front();
            for (auto& e : gr[v]) {
                if (e.cp != e.fl) {
                    if (dist[e.to] > dist[v] + 1) {
                        dist[e.to] = dist[v] + 1;
                        deque.push_back(e.to);
                    }
                }
            }
        }
    }

    void push(Edge& e, int dlt) {
        e.fl += dlt;
        gr[e.to][e.id].fl -= dlt;
    }

    int dfs(int v, int min) {
        if (v == T || min == 0) {
            return min;
        }
        for (int& i = used[v]; i < gr[v].size(); i++) {
            auto& e = gr[v][i];
            if (e.fl != e.cp && dist[e.to] == dist[v] + 1) {
                int res = dfs(e.to, std::min(min, e.cp - e.fl));
                if (res > 0) {
                    push(e, res);
                    return res;
                }
            }
        }
        return 0;
    }

    int findMaxFlow() {
        bfs(S);
        while (dist[T] != n) {
            used.assign(n, 0);
            int val = 0;
            while (val = dfs(S, 1e9)) {
                flow += val;
                assert(flow < 1e7);
            }
            bfs(S);
        }
        return flow;
    }
};

int putaway(int n, int m, int q, int x[], int y[], int W[], int S[]) {
    std::vector<std::pair<int, int>> toys(q);
    for (int i = 0; i < q; i++) {
        toys[i] = {W[i], S[i]};
    }
    // std::vector<int> x(X, X + n);
    // std::vector<int> y(Y, Y + m);

    std::sort(x, x + n);
    std::sort(y, y + m);
    // x.erase(std::unique(x.begin(), x.end()), x.end());
    // y.erase(std::unique(y.begin(), y.end()), y.end());

    for (auto [w, s] : toys) {
        if ((n == 0 || w >= x[n - 1]) && (m == 0 || s >= y[m - 1])) {
            return -1;
        }
    }

    Flow fl(2 + n + m + q);
    for (int i = 0; i < q; i++) {
        fl.pre_add_edge(2 + n + m + i, 1, 1);

        int it_x = std::lower_bound(x, x + n, toys[i].first + 1) - x;
        int it_y = std::lower_bound(y, y + m, toys[i].second + 1) - y;
        if (it_x != n)
            fl.pre_add_edge(2 + it_x, 2 + n + m + i, 1);
        if (it_y != m)
            fl.pre_add_edge(2 + n + it_y, 2 + n + m + i, 1);
    }
    for (int i = 1; i < n; i++) {
        fl.pre_add_edge(2 + i, 2 + i - 1, 1e9);
    }
    for (int i = 1; i < m; i++) {
        fl.pre_add_edge(2 + n + i, 2 + n + i - 1, 1e9);
    }
    for (int i = 0; i < n; i++) {
        fl.pre_add_edge(0, 2 + i, 1);
    }
    for (int i = 0; i < m; i++) {
        fl.pre_add_edge(0, 2 + n + i, 1);
    }

    fl.init_gr();
    for (int i = 0; i < q; i++) {
        fl.add_edge(2 + n + m + i, 1, 1);

        int it_x = std::lower_bound(x, x + n, toys[i].first + 1) - x;
        int it_y = std::lower_bound(y, y + m, toys[i].second + 1) - y;
        if (it_x != n)
            fl.add_edge(2 + it_x, 2 + n + m + i, 1);
        if (it_y != m)
            fl.add_edge(2 + n + it_y, 2 + n + m + i, 1);
    }

    for (int i = 1; i < n; i++) {
        fl.add_edge(2 + i, 2 + i - 1, 1e9);
    }
    for (int i = 1; i < m; i++) {
        fl.add_edge(2 + n + i, 2 + n + i - 1, 1e9);
    }
    int ans = 1;
    for (int i = 0; i < n; i++) {
        fl.add_edge(0, 2 + i, 1);
    }
    for (int i = 0; i < m; i++) {
        fl.add_edge(0, 2 + n + i, 1);
    }

    while (fl.findMaxFlow() < q) {
        // for (int i = 0; i < n; i++) {
        //     fl.add_edge(0, 2 + i, 1);
        // }
        // for (int i = 0; i < m; i++) {
        //     fl.add_edge(0, 2 + n + i, 1);
        // }
        for (auto& e : fl.gr[0]) {
            e.cp++;
            fl.gr[e.to][e.id].cp++;
            fl.gr[e.to][e.id].fl++;
        }

        ans++;
        assert(ans <= q);
    }

    return ans;
}