#include "robots.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int weakN, smallN, toyN;
int const NMAX = 5e4;
int weak[1 + NMAX];
int small[1 + NMAX];
int const TMAX = 1e6;
int ind[1 + TMAX];
int weight[1 + TMAX];
int volume[1 + TMAX];
bool compareWeight(int a, int b) {
return weight[a] < weight[b];
}
bool canSolve(int timer) {
int j = 0;
priority_queue <pair <int, int>> pq;
for(int i = 1;i <= weakN;i++) {
while(weight[ind[j]] < weak[i] && j <= toyN) {
pq.push({volume[ind[j]], ind[j]});
j++;
}
for(int k = 1;k <= timer && !pq.empty();k++) {
pq.pop();
}
}
while(j <= toyN) {
pq.push({volume[ind[j]], ind[j]});
j++;
}
for(int i = smallN;i >= 1;i--) {
for(int k = 1;k <= timer && !pq.empty();k++) {
if(pq.top().first >= small[i]) {
return false;
}
pq.pop();
}
}
return true;
}
int cautbin(int from, int to) {
if(from == to) {
return from;
} else {
int mid = (from + to) / 2; // 0 1 -> 0
if(canSolve(mid)) {
return cautbin(from, mid); // 0 0
}else {
return cautbin(mid+1, to); // 1 1
}
}
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
weakN = A;
smallN = B;
toyN = T;
for(int i = 1;i <= weakN;i++) {
weak[i] = X[i-1];
}
for(int i = 1;i <= smallN;i++) {
small[i] = Y[i-1];
}
for(int i = 1;i <= toyN;i++) {
volume[i] = S[i-1];
weight[i] = W[i-1];
ind[i] = i;
}
sort(ind+1, ind+toyN+1, compareWeight);
sort(weak+1, weak+weakN+1);
sort(small+1, small+smallN+1);
int ans = cautbin(1, toyN);
if(canSolve(ans) == false) {
return -1;
}
return ans;
}
