#include <bits/stdc++.h>
#include <robots.h>
using namespace std;
using ll = long long;
struct Toy {
ll weight, size, index;
};
bool cmpWeight(Toy& a, Toy& b) {
if(a.weight == b.weight) return a.size > b.size;
return a.weight < b.weight;
}
bool cmpSize(Toy& a, Toy& b){
if(a.size == b.size) return a.weight > b.weight;
return a.size > b.size;
}
ll toyCount;
vector<ll> robotWeights, robotSizes;
vector<Toy> toyWeights, toySizes;
bool isValidTime(ll time) {
vector<bool> completedToys(toyCount);
priority_queue<pair<ll,ll>> pq;
ll curToyIndex = 0;
for (int curRobot = 0; curRobot < robotWeights.size(); ++curRobot) {
ll curWeightLimit = robotWeights[curRobot];
while(curToyIndex < toyCount) {
Toy& curToy = toyWeights[curToyIndex];
if(curToy.weight >= curWeightLimit) break;
if(completedToys[curToy.index]) continue;
pq.emplace(curToy.size, curToy.index);
++curToyIndex;
}
ll toysPickedUp = 0;
while(!pq.empty() && toysPickedUp < time) {
ll curToyIndex = pq.top().second; pq.pop();
if(completedToys[curToyIndex]) continue;
++toysPickedUp;
completedToys[curToyIndex] = true;
}
}
curToyIndex = 0;
for (int curRobot = 0; curRobot < robotSizes.size(); ++curRobot) {
ll curSizeLimit = robotSizes[curRobot];
ll toysPickedUp = 0;
while(curToyIndex < toyCount) {
Toy& curToy = toyWeights[curToyIndex];
if(completedToys[curToy.index]) {
++curToyIndex;
continue;
}
if(toysPickedUp == time) break;
if(curToy.size >= curSizeLimit) return false;
++toysPickedUp;
++curToyIndex;
}
}
return true;
}
int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[]) {
toyCount = T;
for (int i = 0; i < A; ++i) {
robotWeights.push_back(X[i]);
}
for (int i = 0; i < B; ++i) {
robotSizes.push_back(Y[i]);
}
for (int i = 0; i < T; ++i) {
toyWeights.push_back({W[i], S[i], i});
}
sort(toyWeights.begin(), toyWeights.end(), cmpWeight);
sort(toySizes.begin(), toySizes.end(), cmpSize);
sort(robotWeights.begin(), robotWeights.end());
sort(robotSizes.rbegin(), robotSizes.rend());
ll minTime = 1, maxTime = T;
while(minTime <= maxTime) {
ll midTime = (maxTime + minTime)/2;
if(isValidTime(midTime)) {
maxTime = midTime - 1;
}
else {
minTime = midTime + 1;
}
}
if(isValidTime(minTime)) return minTime;
else return -1;
}
//int main() {
// ll A,B,T; cin >> A >> B >> T;
// int X[A], Y[B], W[T], S[T];
//
// for (int i = 0; i < A; ++i) {
// cin >> X[i];
// }
// for (int i = 0; i < B; ++i) {
// cin >> Y[i];
// }
//
// for (int i = 0; i < T; ++i) {
// cin >> W[i] >> S[i];
// }
//
// cout << putaway(A,B,T,X,Y,W,S) << '\n';
//}
