#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int n, m, t;
int x[MAXN], y[MAXN];
int freq[MAXN];
int bb();
bool test(int val);
struct point{
int x, y, xID, yID;
point(int _x = 0, int _y = 0, int _xID = 0, int _yID = 0){
x = _x, y = _y, xID = _xID, yID = _yID;
}
bool operator <(point a){
if(xID == a.xID) return yID < a.yID;
return xID < a.xID;
}
} v[MAXN];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n = A, m = B, t = T;
for(int i = 0; i < n; i++)
x[i] = X[i];
for(int i = 0; i < m; i++)
y[i] = Y[i];
sort(x, x + n);
sort(y, y + m);
for(int i = 0; i < t; i++){
int auxX = upper_bound(x, x + n, W[i]) - x;
auxX = n - auxX - 1;
int auxY = upper_bound(y, y + m, S[i]) - y;
auxY = m - auxY - 1;
v[i] = point(W[i], S[i], auxX, auxY);
}
reverse(x, x + n);
reverse(y, y + m);
sort(v, v + t);
return bb();
}
int bb(){
int ini = 1, fim = t;
if(!test(t + 1)) return -1;
while(ini != fim){
int mid = (ini + fim) >> 1;
if(test(mid)) fim = mid;
else ini = mid + 1;
}
return ini;
}
bool test(int val){
if(m == 0){
int naoPego = 0;
for(int i = 0; i < n; i++){
if(v[naoPego].x >= x[i]) return 0;
naoPego += val;
if(naoPego >= t) return 1;
}
return 0;
}
for(int i = 0; i < m; i++)
freq[i] = 0;
int it1 = 0;
multiset<int> sobra;
multiset<int> pegando;
int podePega = val;
while(it1 != t && v[it1].xID == -1)
freq[v[it1++].yID + 1]++;
for(int i = 0; i < n; i++){
while(it1 != t && v[it1].xID == i && podePega)
podePega--, it1++;
while(it1 != t && v[it1].xID == i)
freq[v[it1++].yID + 1]++;
podePega += val;
}
podePega = val;
if(freq[0] > 0) return 0;
for(int i = 0; i < m; i++){
if(freq[i + 1] > podePega) return 0;
podePega += val - freq[i + 1];
}
return 1;
}
