#include "robots.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
vector<int> x,y;
vector<pair<int,int>> toys;
int a,b,t;
int cnt[N];
int deltime[N];
vector<int> v[N];
bool ck(int x){
if(b == 1){
int tot = 0;
for(int i = 0;i<t;i++){
tot++;
long long val = (long long)cnt[i] * x;
while(val && tot){
val--;
tot--;
}
}
return tot == 0;
}
priority_queue<int> rem;
for(int i = 0;i<t;i++){
rem.push(toys[i].second);
long long val = (long long)cnt[i] * x;
while(val && rem.size()){
val--;
rem.pop();
}
}
for(int i = b-1;i>=0;i--){
int val = x;
while(val && rem.size() && rem.top() < y[i]){
val--;
rem.pop();
}
}
return rem.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
x.push_back(1);
y.push_back(1);
for(int i = 0;i<A;i++){
x.push_back(X[i]);
}
for(int i = 0;i<B;i++){
y.push_back(Y[i]);
}
vector<int> compressx = x,compressy = y;
for(int i = 0;i<T;i++){
toys.push_back({W[i],S[i]});
compressx.push_back(W[i]);
compressy.push_back(S[i]);
}
sort(compressx.begin(),compressx.end());
sort(compressy.begin(),compressy.end());
compressx.resize(unique(compressx.begin(),compressx.end())-compressx.begin());
compressy.resize(unique(compressy.begin(),compressy.end())-compressy.begin());
for(auto &u:x){
u = lower_bound(compressx.begin(),compressx.end(),u) - compressx.begin();
}
for(auto &u:y){
u = lower_bound(compressy.begin(),compressy.end(),u) - compressy.begin();
}
for(auto &u:toys){
u.first = lower_bound(compressx.begin(),compressx.end(),u.first) - compressx.begin();
u.second = lower_bound(compressy.begin(),compressy.end(),u.second) - compressy.begin();
}
a = A+1;
b = B+1;
t = T;
sort(x.begin(),x.end());
sort(y.begin(),y.end());
sort(toys.begin(),toys.end());
for(auto u:toys){
if(u.first >= x.back() && u.second >= y.back()){
return -1;
}
}
for(int i = 0;i<t;i++){
v[toys[i].second].push_back(i);
}
int pt = 0;
for(auto u:x){
while(pt < t && toys[pt].first < u){
pt++;
}
if(pt)
cnt[pt-1]++;
}
int l = 1,r = t;
while(l < r){
int m = (l+r)/2;
if(ck(m)){
r = m;
}
else l = m+1;
}
return l;
}
