#include "robots.h"
#include <algorithm>
#define MAXN 50000
#define MAXT 1000000
int A, B, T, viz[MAXT];
int timp, S[MAXT], W[MAXT], ind1[MAXT], ind2[MAXT];
int heap[MAXT + 1], X[MAXN], Y[MAXN];
bool cmpS(const int &a, const int &b) {
return S[a] < S[b];
}
bool cmpW(const int &a, const int &b) {
return W[a] < W[b];
}
inline void urcare(int p) {
while (p > 1 && W[heap[p]] > W[heap[p / 2]]) {
std::swap(heap[p], heap[p / 2]);
p /= 2;
}
}
inline void coborare(int p) {
int q;
bool f = 1;
while (f && (q = 2 * p) <= heap[0]) {
if (q < heap[0] && W[heap[q + 1]] > W[heap[q]])
q++;
if (W[heap[q]] > W[heap[p]]) {
std::swap(heap[p], heap[q]);
p = q;
} else
f = 0;
}
}
inline bool check(int k) {
int p = 0, cnt = 0, q = 0;
timp++;
heap[0] = 0;
for (int i = 0; i < B; i++) {
while (p < T && S[ind2[p]] <= Y[i]) {
heap[++heap[0]] = ind2[p];
urcare(heap[0]);
p++;
}
int u = k;
while (heap[0] > 0 && u > 0) {
viz[heap[1]] = timp;
std::swap(heap[1], heap[heap[0]]);
heap[0]--;
u--;
cnt++;
coborare(1);
}
}
p = 0;
for (int i = 0; i < A; i++) {
while (p < T && W[ind1[p]] <= X[i]) {
q += viz[ind1[p]] != timp;
p++;
}
if (q > k)
q -= k, cnt += k;
else {
cnt += q;
q = 0;
}
}
return cnt == T;
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
A = a;
B = b;
T = t;
for (int i = 0; i < A; i++)
X[i] = x[i];
for (int i = 0; i < B; i++)
Y[i] = y[i];
for (int i = 0; i < T; i++)
ind1[i] = ind2[i] = i, W[i] = w[i], S[i] = s[i];
std::sort(ind1, ind1 + T, cmpW);
std::sort(ind2, ind2 + T, cmpS);
std::sort(X, X + A);
std::sort(Y, Y + b);
bool ok = 1;
for (int i = 0; i < T; i++)
if ((A == 0 || W[i] > X[A - 1]) && (B == 0 || S[i] > Y[B - 1]))
ok = 0;
if (!ok)
return -1;
int rez = 0;
for (int pas = 1 << 19; pas; pas >>= 1)
if (!check(rez + pas))
rez += pas;
return rez + 1;
}
