#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
struct FlowEdge {
int u, v;
int cap, flow = 0;
FlowEdge (int from, int to, long long w) : u (from), v (to), cap (w) {}
};
struct EdmondsKarp {
const int flow_inf = 1e9;
vector<FlowEdge> edge;
vector< vector<int> > g;
vector<int> parent;
int m, source, sink;
EdmondsKarp (int n, int s, int t) : m(0), source (s), sink (t) {
edge.clear();
g.clear(); g.resize(n);
parent.clear(); parent.resize(n);
}
void addEdge (int u, int v, int w) {
edge.emplace_back(u, v, w);
edge.emplace_back(v, u, 0);
g[u].emplace_back(m);
g[v].emplace_back(m + 1);
m += 2;
}
int bfs () {
fill (parent.begin(), parent.end(), -1);
queue<pair<int, int > > q;
q.push({source, flow_inf});
while (!q.empty()) {
int node = q.front().first;
int mn = q.front().second;
q.pop();
if (node == sink) return mn;
if (mn == 0) return 0;
for (auto to : g[node]) {
if (parent[edge[to].v] == -1 && edge[to].cap - edge[to].flow >= 1) {
parent[edge[to].v] = to;
q.push({edge[to].v, min (mn, edge[to].cap - edge[to].flow)});
}
}
}
return 0;
}
int flow () {
int f = 0;
while (int add = bfs ()) {
f += add;
int cur = sink;
while (cur != source) {
int node = parent[cur];
edge[node].flow += add;
edge[node ^ 1].flow -= add;
cur = edge[parent[cur]].u;
}
}
return f;
}
};
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
vector<int> weak, small;
for (int i = 0; i < A; i++) {
weak.emplace_back(X[i]);
}
for (int i = 0; i < B; i++) {
small.emplace_back(Y[i]);
}
vector<pair<int, int>> arr(T);
for (int i = 0; i < T; i++) {
arr[i] = {W[i], S[i]};
}
//~ sort(weak.begin(), weak.end());
//~ sort(small.begin(), small.end());
auto works = [&](int time) {
EdmondsKarp solve(T + A + B + 10, 0, 1);
int cur = 2;
for (int i = 0; i < A; i++) {
solve.addEdge(0, cur, time);
for (int j = 0; j < T; j++) {
if (arr[j].first < X[i]) {
solve.addEdge(cur, A + B + 5 + j, 1);
}
}
++cur;
}
for (int i = 0; i < B; i++) {
solve.addEdge(0, cur, time);
for (int j = 0; j < T; j++) {
if (arr[j].second < Y[i]) {
solve.addEdge(cur, A + B + 5 + j, 1);
}
}
++cur;
}
for (int j = 0; j < T; j++) {
solve.addEdge(A + B + 5 + j, 1, 1);
}
return (solve.flow() == T);
};
const int INF = 1e4 + 5;
int lo = 0, hi = INF + 10;
while(lo < hi) {
const int mid = lo + (hi - lo) / 2;
if (works(mid)) hi = mid;
else lo = mid + 1;
}
return (hi > INF ? -1 : hi);
}
