#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1123456;
//x -> w
//y -> s
int x[MAXN], y[MAXN], w[MAXN], s[MAXN];
int va[MAXN], vb[MAXN];
int n, a, b;
int marc[MAXN];
bool cmp1(int a, int b) {
return w[a] < w[b];
}
bool cmp2(int a, int b) {
return s[a] < s[b];
}
bool teste(int t) {
priority_queue < pair <int, int> > s1;
int ts = 0;
int cur = 0;
for(int i = 0; i < a; i++) {
while(w[va[cur]] < x[i]) {
s1.push(make_pair(s[va[cur]], va[cur]));
}
int cs = 0;
while(cs < t) {
if(s1.empty()) break;
pair <int, int> temp = s1.top();
s1.pop();
cs++;
marc[temp.second] = 1;
}
}
priority_queue <pair <int, int> > s2;
for(int i = 0; i < n; i++) {
if(marc[i] == 0) s2.push(make_pair(-s[i], i));
}
for(int i = b - 1; i >= 0; i--) {
int cs = 0;
while(cs < t) {
if(s2.empty()) break;
pair <int, int> temp = s2.top();
if(-temp.first >= y[i]) break;
s2.pop();
cs++;
}
}
return ts == n;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n = T;
a = A; b = B;
for(int i = 0; i < T; i++) {
va[i] = i;
vb[i] = i;
w[i] = W[i]; s[i] = S[i];
}
sort(va, va + n, cmp1);
sort(vb, vb + n, cmp2);
for(int i = 0; i < a; i++) x[i] = X[i];
for(int i = 0; i < b; i++) y[i] = Y[i];
sort(x, x + a); sort(y, y + b);
int ini = 1, fim = MAXN;
while(ini < fim) {
for(int i = 0; i < n; i++) marc[i] = 0;
int m = (ini + fim) / 2;
if(teste(m)) {
fim = m;
}
else ini = m + 1;
}
if(ini == MAXN) ini = -1;
return ini;
}
