#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
const int MAXN = 100010;
const int MAXT = 1000010;
int a, b, n, x[MAXN], y[MAXN], w[MAXT], s[MAXT];
bool valid(int mns)
{
vector<pair<int, int> > p;
for(int i = 0; i < n; i++) p.push_back({w[i], i});
sort(p.begin(), p.end());
int id = 0;
set<pair<int, int> > xs, ys;
set<pair<int, int> > :: iterator it;
for(int i = 0; i < (int) p.size(); i++)
{
int xcur = p[i].first;
int j = p[i].second;
int ycur = s[j];
while(id < a && xcur > x[id])
{
for(int k = 0; k < mns; k++)
if(!ys.empty())
ys.erase(*(--ys.end()));
id++;
}
ys.insert({ycur, j});
}
while(id < a)
{
for(int k = 0; k < mns; k++)
if(!ys.empty())
ys.erase(*(--ys.end()));
id++;
}
p.clear();
for(it = ys.begin(); it != ys.end(); it++)
p.push_back(*it);
id = 0;
for(int i = 0; i < (int) p.size(); i++)
{
int ycur = p[i].first;
int j = p[i].second;
int xcur = w[j];
while(id < b && ycur > y[id])
{
for(int k = 0; k < mns; k++)
if(!xs.empty())
xs.erase(*(--xs.end()));
id++;
}
xs.insert({xcur, j});
}
while(id < b)
{
for(int k = 0; k < mns; k++)
if(!xs.empty())
xs.erase(*(--xs.end()));
id++;
}
if(xs.empty()) return true;
return false;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
a = A, b = B, n = T;
for(int i = 0; i < A; i++) x[i] = X[i];
for(int i = 0; i < B; i++) y[i] = Y[i];
for(int i = 0; i < T; i++) w[i] = W[i], s[i] = S[i];
sort(x, x + A);
sort(y, y + B);
int bg = 0, ed = MAXT;
while(bg < ed)
{
int mid = (bg == ed - 1) ? bg : (bg + ed) >> 1;
if(valid(mid)) ed = mid;
else bg = mid + 1;
}
return (bg == MAXT) ? -1 : bg;
}
