#include "robots.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
typedef pair<int,int> PI;
int Nw, Ns;
int weak[50005];
int small[50005];
int Nt;
// Weight, Size
PI toys[1000005];
bool check(int poop){
// cout << "checking " << poop << '\n';
deque<PI> toyList;
for(int i = 0; i < Nt; i++) toyList.push_back(toys[i]);
priority_queue<PI, vector<PI>, decltype([](PI &a, PI &b){return a.second<b.second;})> pqBigSize;
int total = 0;
for(int i = 0; i < Nw; i++){
int count = 0;
while(!toyList.empty() && toyList.front().first < weak[i]){
pqBigSize.push(toyList.front());
toyList.pop_front();
}
// cout << "W(" << weak[i] << "): ";
for(int j = 0; j < poop && !pqBigSize.empty(); j++){
// cout << "(" << pqBigSize.top().first << ", " << pqBigSize.top().second << ") ";
pqBigSize.pop();
total++;
}
// cout << '\n';
}
priority_queue<PI, vector<PI>, decltype([](PI &a, PI &b){return a.second>b.second;})> pqSmallSize;
while(!toyList.empty()){
pqSmallSize.push(toyList.front());
toyList.pop_front();
}
while(!pqBigSize.empty()){
pqSmallSize.push(pqBigSize.top());
pqBigSize.pop();
}
for(int i = 0; i < Ns; i++){
// cout << "S(" << small[i] << "): ";
for(int j = 0; j < poop && !pqSmallSize.empty() && pqSmallSize.top().second < small[i]; j++){
// cout << "(" << pqSmallSize.top().first << ", " << pqSmallSize.top().second << ") ";
total++;
pqSmallSize.pop();
}
// cout << '\n';
}
// cout << "total: " << total << '\n';
bool ans = pqSmallSize.empty();
// cout << "Remain: ";
// while(!pqSmallSize.empty()){
// cout << "(" << pqSmallSize.top().first << ", " << pqSmallSize.top().second << ") ";
// pqSmallSize.pop();
// }
// cout << '\n';
return ans;
}
int putaway(int A, int B, int T,
int X[], int Y[], int W[], int S[]){
Nw = A;
Ns = B;
for(int i = 0; i < Nw; i++) weak[i] = X[i];
for(int i = 0; i < Ns; i++) small[i] = Y[i];
Nt = T;
for(int i = 0; i < Nt; i++){
toys[i] = {W[i], S[i]};
}
sort(weak, weak+Nw);
sort(small, small+Ns);
//sort by weight
sort(toys, toys+Nt, [](pair<int,int> a, pair<int,int> b) {return a.first<b.first;});
// cout << "Toys\n";
// for(int i = 0; i < Nt; i++){
// cout << "(" << toys[i].first << ", " << toys[i].second << ") ";
// }
// cout << '\n';
// if(!check(T+5)) return -1;
int low = 1;
int high = T+5;
while(high - low > 1){
int mid = low + (high - low) / 2;
if(check(mid)) high = mid;
else low = mid;
}
if(check(high)) return -1;
return high;
}
