#include<bits/stdc++.h>
using namespace std;
#include "robots.h"
bool can(vector<int> X, vector<int> Y, vector<pair<int, int> > Z, int T)
{
int ztp = 0;
priority_queue<pair<int, int> > Q;
for(auto y: Y)
{
while(ztp<(int)Z.size() && Z[ztp].second < y)
Q.emplace(Z[ztp++]);
for(int i=0; i<T && !Q.empty(); ++i)
Q.pop();
}
while(ztp<(int)Z.size()) Q.emplace(Z[ztp++]);
vector<int> remainX;
while(!Q.empty())
{
remainX.push_back(Q.top().first);
Q.pop();
}
sort(remainX.begin(), remainX.end());
int xtp = 0;
for(auto x: X)
for(int i=0; i<T && xtp != (int)remainX.size() && remainX[xtp] < x; ++i)
++xtp;
return xtp == (int)remainX.size();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int lo = 0; //impos
int hi = T+1; //pos
vector<int> _X(X, X+A), _Y(Y, Y+B);
vector<pair<int, int> > ws;
for(int i=0; i<T; ++i)
ws.emplace_back(W[i], S[i]);
//sort X, Y, ws according to second value
sort(_X.begin(), _X.end());
sort(_Y.begin(), _Y.end());
sort(ws.begin(), ws.end(), [](pair<int, int> a, pair<int, int> b)
{
return a.second < b.second;
});
while(lo+1!=hi)
{
int mi = (lo+hi)>>1;
if(can(_X, _Y, ws, mi)) hi = mi;
else lo = mi;
}
if(hi == T+1) return -1;
return hi;
}
