#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
struct Robot{
int x, y, id;
};
const int T_MAX = 1e6;
const int N_MAX = 5e4 + 11;
int W[T_MAX], S[T_MAX];
int A, B, T;
vector<int> rx, ry;
bool thrown[T_MAX];
struct BIT{
int t[T_MAX];
void init(){
fill(t, t + T_MAX, 0);
}
void add(int p, int v){
++p;
for(int i = p; i < T_MAX; i += i & -i){
t[i] += v;
}
}
int qry(int p){
++p; int res = 0;
for(int i = p; i; i -= i & -i){
res += t[i];
}
return res;
}
int bs(int v){
int r = 0, s = 0;
for(int j = 19; j >= 0; j--){
if(s + t[r + (1 << j)] < v) s += t[r + (1 << j)], r += (1 << j);
}
return r;
}
} bit;
bool can(int K){
fill(thrown, thrown + T_MAX, 0);
int ri = 0, s = 0; bit.init();
for(int i = 0; i < A; i++){
while(ri < T && W[rx[ri]] <= i){
if(thrown[rx[ri]]) { ++ri; continue; }
bit.add(rx[ri], 1); ++ri; ++s;
}
for(int j = 0; j < K && s > 0; j++){
int p = bit.bs(s); thrown[p] = true; --s;
bit.add(p, -1);
}
}
ri = s = 0; bit.init();
for(int i = 0; i < B; i++){
while(ri < T && S[ry[ri]] <= i){
if(thrown[ry[ri]]) { ++ri; continue; }
bit.add(ry[ri], 1); ++ri; ++s;
}
for(int j = 0; j < K && s > 0; j++){
int p = bit.bs(s); thrown[p] = true; --s;
bit.add(p, -1);
}
}
bool done = true;
for(int i = 0; i < T; i++){
if(!thrown[i]) done = false;
}
return done;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
::A = A; ::B = B; ::T = T; sort(X, X + A); sort(Y, Y + B);
for(int i = 0; i < T; i++){
::W[i] = upper_bound(X, X + A, W[i]) - X;
::S[i] = upper_bound(Y, Y + B, S[i]) - Y;
if(::W[i] == A && ::S[i] == B) return -1;
}
for(int i = 0; i < T; i++) rx.push_back(i); ry = rx;
sort(rx.begin(), rx.end(), [](int a, int b){
return ::W[a] < ::W[b];
});
sort(ry.begin(), ry.end(), [](int a, int b){
return ::S[a] < ::S[b];
});
int L = 0, R = T;
while(L != R){
int M = (L + R) / 2;
if(can(M)){
R = M;
}else{
L = M + 1;
}
}
return L;
}
