#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int w[1000005], s[1000005];
bool cmpw(int a, int b){
if (w[a] != w[b]) return w[a] < w[b];
else return s[a] < s[b];
}
bool cmps(int a, int b){
return s[a] <= s[b];
}
bool cando(int x, int A, int B, int T, int X[], int Y[], int W[], int S[]){
//printf("\t\t\t\tTesting %d\n",x);
vector<int> v(T);
for (int i = 0; i < T; i++) v[i] = i;
sort(v.begin(),v.end(),cmpw);
int curT = 0, curA = 0;
priority_queue<int> pq;
while (curT < T && curA < A){
//printf("toy %d weight %d robot %d\n",v[curT],W[v[curT]],curA);
if (X[curA] <= W[v[curT]]){
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d weight %d\n",curA,pq.top().second,pq.top().first);
pq.pop();
}
curA++;
}
else{
pq.push(S[v[curT]]);
curT++;
}
}
while (curA++ < A){
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d size %d\n",curA,pq.top().second,pq.top().first);
pq.pop();
}
}
while (curT < T){
//printf("toy %d not taken by weight\n",v[curT]);
pq.push(S[v[curT++]]);
}
int curB = B-1;
while (curB && pq.size()){
//printf("toy %d size %d robot %d\n",v2[curT],S[v2[curT]],curB);
if (Y[curB] <= pq.top()) return false;
else{
int num = 0;
while (num++ < x && pq.size()){
//printf("robot %d takes %d size %d\n",curB,pq.top().second,pq.top().first);
pq.pop();
}
curB--;
}
}
return pq.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
for (int i = 0; i < T; i++){
w[i] = W[i];
s[i] = S[i];
}
sort(X,X+A);
sort(Y,Y+B);
int lo = 0, hi = T+1;
while (lo + 1 < hi){
//printf("%d %d\n",lo,hi);
int mid = (lo+hi)/2;
if (cando(mid,A,B,T,X,Y,W,S)){
hi = mid;
}
else lo = mid;
}
if (lo + 1 == hi){
//printf("%d %d\n",lo,hi);
if (cando(lo,A,B,T,X,Y,W,S)) hi = lo;
else lo = hi;
}
if (lo == T+1) return -1;
return lo;
}
