#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7;
int A, B, n, X[LIM], Y[LIM], odw[LIM], F[LIM], ile[LIM], sum[LIM];
pair<int,int>T[LIM];
int fnd(int x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
ile[fnd(b)]+=ile[fnd(a)];
F[fnd(a)]=fnd(b);
}
bool check(int x) {
rep(i, B+1) {
F[i]=i;
ile[i]=x;
}
ile[B]=0;
rep(i, A) sum[i]=0;
rep(i, n) {
while(ile[fnd(T[i].nd)]==0) {
if(fnd(T[i].nd)==B) break;
uni(T[i].nd, fnd(T[i].nd)+1);
}
if(ile[fnd(T[i].nd)]) {
--ile[fnd(T[i].nd)];
continue;
}
++sum[T[i].st];
}
ll akt=-x;
for(int i=A; i>=0; --i) {
akt+=x;
akt-=sum[i];
if(akt<0) return false;
}
return true;
}
int putaway(int Ai, int Bi, int Ti, int Xi[], int Yi[], int Wi[], int Si[]) {
A=Ai; B=Bi; n=Ti;
rep(i, A) X[i]=Xi[i];
rep(i, B) Y[i]=Yi[i];
rep(i, n) T[i]={Wi[i], Si[i]};
sort(T, T+n);
sort(X, X+A);
sort(Y, Y+B);
rep(i, n) if(T[i].st>=X[A-1] && T[i].nd>=Y[B-1]) return -1;
rep(i, n) {
int po=0, ko=A;
while(po<ko) {
int sr=(po+ko+1)/2;
if(T[i].st>=X[sr]) ko=sr-1; else po=sr;
}
T[i].st=po;
po=0; ko=B;
while(po<ko) {
int sr=(po+ko+1)/2;
if(T[i].nd>=Y[sr]) ko=sr-1; else po=sr;
}
T[i].nd=po;
}
sort(T, T+n);
reverse(T, T+n);
int po=1, ko=n;
while(po<ko) {
int sr=(po+ko)/2;
if(check(sr)) ko=sr; else po=sr+1;
}
return po;
}
