#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int k_T = 1e6 + 3;
int a, b, t;
int *x, *y, *w, *s;
array<int, 2> p1[k_T], p2[k_T];
bool used[k_T];
bool check(int mid){
for(int i = 0; i < t; ++i)
used[i] = false;
int j = 0;
set<array<int, 2>> s;
for(int i = 0; i < b; ++i){
while(j != t && y[i] > p2[j][0]){
s.insert({w[p2[j][1]], p2[j][1]});
j++;
}
for(int k = 0; k < mid && !s.empty(); ++k){
auto arr = *s.rbegin();
s.erase(arr);
used[arr[1]] = true;
}
}
j = 0;
vector<int> idx;
for(int i = 0; i < a; ++i){
while(j != t && x[i] > p1[j][0]){
if(!used[p1[j][1]])
idx.push_back(p1[j][1]);
j++;
}
for(int k = 0; k < mid && !idx.empty(); ++k){
used[idx.back()] = true;
idx.pop_back();
}
}
for(int i = 0; i < t; ++i)
if(!used[i])
return false;
return true;
}
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;
sort(x, x + a);
sort(y, y + b);
for(int i = 0; i < t; ++i){
p1[i] = {w[i], i};
p2[i] = {s[i], i};
}
sort(p1, p1 + t);
sort(p2, p2 + t);
int l = 1, r = t + 1;
while(l != r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(l == t + 1) l = -1;
return l;
}
