/*
bro what the hell is this
binary search again?
*/
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
vector<pair<int, int>> toys;
vector<int> weightLim;
vector<int> weightLimCnt;
vector<int> sizeLim;
vector<int> sizeLimCnt;
bool check(int cnt, int &a, int &b, int &t) {
int weakIdx = 0;
int end = t-1;
if(a != 0) while(toys[end].first >= weightLim[a-1]) {
int l = -1, r = b;
while(l + 1 < r) {
int m = (l+r)/2;
if((sizeLim[m] >= toys[end].second) and (sizeLimCnt[m] < cnt)) r = m;
else l = m;
}
if(r == b) return false;
else {sizeLimCnt[r]++;}
end--;
}
for(int i = 0; i <= end; i++) {
/*
greedily assign to someone who can carry it (size constraint)
otherwise, give it to the max person with weight constraint
*/
int l = -1, r = b;
while(l + 1 < r) {
int m = (l+r)/2;
if((sizeLim[m] >= toys[i].second) and (sizeLimCnt[m] < cnt)) r = m;
else l = m;
}
if (r == b) { // assign it to max weight
if(a == 0) return false;
while((weightLim[weakIdx] < toys[i].first or weightLimCnt[weakIdx] >= cnt) and weakIdx < a) weakIdx++;
if(weakIdx < a) {
weightLimCnt[weakIdx]++;
if(weightLimCnt[weakIdx] >= cnt) weakIdx++;
} else return false;
} else {sizeLimCnt[r]++;}
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
// long ahh signature
for(int i = 0; i < T; i++) {
toys.push_back({W[i], S[i]});
}
for(int i = 0; i < A; i++) {
weightLim.push_back(X[i]);
}
for(int i = 0; i < B; i++) {
sizeLim.push_back(Y[i]);
}
sort(toys.begin(), toys.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {return a.first == b.first ? a.second < b.second : a.first < b.first;});
sort(weightLim.begin(), weightLim.end(), less<int>());
sort(sizeLim.begin(), sizeLim.end(), less<int>());
ll l = 0, r = T+1;
while(l + 1 < r) {
weightLimCnt = vector(A, 0);
sizeLimCnt = vector(B, 0);
ll m = (l+r)>>1;
if(check(m, A, B, T)) {
r = m;
} else {
l = m;
}
}
if(r == T+1) {
return -1;
} else return r;
}
