#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
using pii = pair<int, int>;
const int N = 50010;
const int MT = 1000010;
const int INF = 2e9+1;
int A, B, T;
int *X, *Y, *W, *S, wix[MT], six[MT], used[MT], tick=0;
bool check(int tim)
{
++tick;
int tt = 0;
// weak robot matching
int j = 0;
priority_queue<pii> Q;
for (int i = 0; i < A; ++i) {
while (j < T && W[wix[j]] < X[i]) {
Q.push({S[wix[j]], wix[j]});
++j;
}
for (int cnt = 0; cnt < tim && !Q.empty(); ++cnt) {
used[Q.top().second] = tick;
++tt;
Q.pop();
}
}
// small robot matching
j = 0;
while (!Q.empty()) Q.pop();
for (int i = 0; i < B; ++i) {
while (j < T && S[six[j]] < Y[i]) {
if (used[six[j]] != tick)
Q.push({W[six[j]], six[j]});
++j;
}
for (int cnt = 0; cnt < tim && !Q.empty(); ++cnt) {
used[Q.top().second] = tick;
++tt;
Q.pop();
}
}
return tt == T;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
::A = A, ::B = B, ::T = T, ::X = X, ::Y = Y, ::W = W, ::S = S;
for (int i = 0; i < T; ++i)
six[i] = wix[i] = i;
sort(wix, wix+T, [&] (int a, int b) {
return W[a] < W[b];
});
sort(six, six+T, [&] (int a, int b) {
return S[a] < S[b];
});
sort(X, X+A);
sort(Y, Y+B);
int b = 1, e = T+1;
while (b < e) {
int m = (b+e)/2;
if (check(m))
e = m;
else
b = m+1;
}
return b == T+1 ? -1 : b;
}
