#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
struct event {
int pos, type, num;
};
bool cmp(event e1, event e2) {
if(e1.pos != e2.pos) return e1.pos < e2.pos;
return e1.type < e2.type;
}
bool tryPut(int cnt, int a, int b, int t, int x[], int y[], int w[], int s[]) {
vector < event > E;
for(int i = 0; i < a; i++) E.push_back( { x[i], 0, i } );
for(int i = 0; i < t; i++) {
E.push_back( { w[i], 1, i } );
}
sort(E.begin(), E.end(), cmp);
set < pair < int, int > > toys;
for(auto q: E) {
if(q.type == 0) {
for(int i = 0; toys.size() > 0 && i < cnt; i++) {
toys.erase(toys.find(*toys.rbegin()));
}
}
else {
toys.insert( { s[q.num], q.num } );
}
}
E.clear();
for(int i = 0; i < b; i++) E.push_back( { y[i], 0, i } );
for(auto x: toys) {
int i = x.second;
E.push_back( { s[i], 1, i } );
}
sort(E.begin(), E.end(), cmp);
int sz = 0;
for(auto q: E) {
if(q.type == 0) {
for(int i = 0; sz > 0 && i < cnt; i++) {
sz--;
}
}
else {
sz++;
}
}
return (sz == 0);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int L = 0, R = T + 1;
while(R - L > 1) {
int mid = (L + R) >> 1;
if(tryPut(mid, A, B, T, X, Y, W, S)) R = mid;
else L = mid;
}
if(R == T + 1) return -1;
return R;
}
