#include "robots.h"
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
#define MOD 1000000007
int N, A, B;
int C[1050000];
int F[50000];
vector<P> G[1050000];
vector<int> xs, ys;
bool f(int X) {
priority_queue<P> q;
rep(x, xs.size()) {
for (P y : G[x]) q.push(y);
int times = min(1LL*X*C[x], (long long)N);
while (!q.empty() && times > 0) {
q.pop();
times--;
}
}
for (int i=B-1; i>=0; i--) {
rep(_, X) {
if (q.empty()) return true;
if (q.top()._1 > F[i]) return false;
q.pop();
}
}
return q.empty();
}
int putaway(int AA, int BB, int T, int X[], int Y[], int W[], int S[]) {
N = T, A = AA, B = BB;
rep(i, A) X[i]--;
rep(i, B) Y[i]--;
sort(X, X+A);
sort(Y, Y+B);
int max_x = -1, max_y = -1;
rep(i, A) max_x = max(max_x, X[i]);
rep(i, B) max_y = max(max_y, Y[i]);
rep(i, T) if (W[i] > max_x && S[i] > max_y) return -1;
if (B == 0) {
int t = 0;
multiset<int> vs;
rep(i, T) vs.insert(W[i]);
int l = 0;
while (!vs.empty()) {
t++;
for (int i=l; i<A; i++) {
auto it = vs.upper_bound(X[i]);
if (it == vs.begin()) {
l = i+1;
continue;
}
vs.erase(--it);
}
}
return t;
}
rep(i, A) xs.pb(X[i]);
rep(i, B) ys.pb(Y[i]);
rep(i, N) xs.pb(W[i]), ys.pb(S[i]);
sort(all(xs)); uniq(xs);
sort(all(ys)); uniq(ys);
rep(i, A) X[i] = index(xs, X[i]);
rep(i, B) Y[i] = index(ys, Y[i]);
rep(i, A) C[X[i]]++;
rep(i, B) F[i] = Y[i];
rep(i, N) {
W[i] = index(xs, W[i]);
S[i] = index(ys, S[i]);
G[W[i]].pb(P(S[i], i));
}
int lo = 0, hi = N;
while (hi-lo > 1) {
int mid = (lo+hi)/2;
if (f(mid)) hi = mid;
else lo = mid;
}
return hi;
}
