#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1123456;
//x -> w
//y -> s
int x[MAXN], y[MAXN];
pair <int, int> v[MAXN];
int n, a, b;
multiset <pair <int, int> > :: iterator it;
bool teste(int t) {
multiset <pair <int, int> > sa;
multiset <pair <int, int> > sb;
multiset <int> sz;
for(int i = 0; i < a; i++) sa.insert(make_pair(x[i], t));
for(int i = 0; i < b; i++) sb.insert(make_pair(y[i], t));
for(int i = n - 1; i >= 0; i--) {
it = sa.upper_bound(make_pair(v[i].first, MAXN));
sz.insert(v[i].second);
if(it == sa.end()) {
int a = *(sz.begin());
sz.erase(sz.begin());
it = sb.upper_bound(make_pair(a, MAXN));
if(it == sb.end()) return false;
else {
pair <int, int> temp = *it;
sb.erase(it);
temp.second--;
if(temp.second > 0) sb.insert(temp);
}
}
else {
pair <int, int> temp = *it;
sa.erase(it);
temp.second -= 1;
if(temp.second > 0) {
sa.insert(temp);
}
}
}
return true;
}
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++) {
v[i] = make_pair(W[i], S[i]);
}
sort(v, v + n);
for(int i = 0; i < a; i++) x[i] = X[i];
for(int i = 0; i < b; i++) y[i] = Y[i];
int ini = 1, fim = MAXN;
while(ini < fim) {
int m = (ini + fim) / 2;
if(teste(m)) {
fim = m;
}
else ini = m + 1;
}
if(ini == MAXN) ini = -1;
return ini;
}
