#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;
int marca[MAXN], marcb[MAXN];
multiset <pair <int, int> > :: iterator it;
bool teste(int t) {
if(b == 0) {
int pt = a - 1, at = 0;
for(int i = n - 1; i >= 0; i--) {
if(v[i].first >= x[pt] || pt == -1) {
return false;
}
else {
at++;
if(at == t) {
pt--;
at = 0;
}
}
}
return true;
}
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], i));
for(int i = 0; i < b; i++) sb.insert(make_pair(y[i], i));
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;
marcb[temp.second]++;
if(marcb[temp.second] == t) sb.erase(it);
}
}
else {
pair <int, int> temp = *it;
marca[temp.second]++;
if(marca[temp.second] == t) sa.erase(it);
}
}
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];
sort(x, x + a); sort(y, y + b);
int ini = 1, fim = MAXN;
while(ini < fim) {
for(int i = 0; i < a; i++) marca[i] = 0;
for(int i = 0; i < b; i++) marcb[i] = 0;
int m = (ini + fim) / 2;
if(teste(m)) {
fim = m;
}
else ini = m + 1;
}
if(ini == MAXN) ini = -1;
return ini;
}
