#include "robots.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<pair<int,int> > U;
priority_queue<int> H;
vector<int> P,Q;
bool chk(int v)
{
int i,j,c;
for (i=j=0;i<P.size();i++){
while (j < U.size() && U[j].first < P[i]){
H.push(U[j].second); j++;
}
c = v;
while (c > 0 && !H.empty()){
H.pop(); c--;
}
}
for (;j<U.size();j++) H.push(U[j].second);
for (i=0;i<Q.size();i++){
c = 0;
while (c < v && !H.empty()){
if (H.top() >= Q[i]) return false;
c++; H.pop();
}
if (H.empty()) break;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i;
for (i=0;i<T;i++) U.push_back(make_pair(W[i],S[i]));
sort(U.begin(),U.end());
for (i=0;i<A;i++) P.push_back(X[i]);
sort(P.begin(),P.end());
for (i=0;i<B;i++) Q.push_back(Y[i]);
sort(Q.rbegin(),Q.rend());
int l = 1, r = T, m = 1;
while (l < r){
m = (l + r) / 2;
if (chk(m)) r = m - 1;
else l = m + 1;
}
while (m >= 1 && chk(m)) m--;
while (m <= T && !chk(m)) m++;
if (m > T) m = -1;
return m;
}
