#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a, b, t;
int x[100005];
int y[100005];
pair <int, int> toys[1000005];
bool used[1000005];
struct strukt{
int w;
int s;
int ind;
bool operator<(const strukt& a) const{
return s < a.s;
}
};
priority_queue <strukt> pq;
bool check(int k){
while(!pq.empty()) pq.pop();
for(int i=1; i<=t; i++) used[i] = 0;
int j = 1;
int cnt = 0;
for(int i=1; i<=a; i++){
while(j <= t /*&& toys[j].first < x[i]*/){
if(toys[j].first >= x[i]) break;
pq.push({toys[j].first, toys[j].second, j});
j++;
}
int r = k;
while(r-- && !pq.empty()){
strukt g = pq.top();
pq.pop();
used[g.ind] = 1;
cnt++;
}
}
vector <int> vec;
for(int i=1; i<=t; i++){
if(!used[i]){
vec.push_back(toys[i].second);
}
}
sort(vec.begin(), vec.end());
for(int i=b; i>=1; i--){
int r = k;
while(!vec.empty() && vec[vec.size()-1] < y[i] && r--){
vec.pop_back();
}
}
return vec.empty();
}
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=1; i<=t; i++){
toys[i].first = W[i-1];
toys[i].second = S[i-1];
}
sort(toys+1, toys+1+t);
for(int i=1; i<=a; i++){
x[i] = X[i-1];
}
sort(x+1, x+1+a);
for(int i=1; i<=b; i++){
y[i] = Y[i-1];
}
sort(y+1, y+1+b);
int l = 1, r = T, res = T+1;
while(l <= r){
int mid = (l+r)/2;
if(check(mid)){
res = min(res, mid);
r = mid-1;
}
else l = mid+1;
}
if(res == T+1) return -1;
else return res;
}
