#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int,int> ii;
class ST {
private:
int n,h;
vl st,lz;
const ll STV = -1LL<<62;
int log2(int v) {
if(v <= 1) {return 1;}
return log2(v/2)+1;
}
void ap(int p, ll val) {
st[p] += val;
if(p < n) {lz[p] += val;}
}
void build(int p) {
while(p > 1) {
p >>= 1;
if(p >= n) {continue;}
st[p] = max(st[p<<1],st[p<<1|1])+lz[p];
}
}
void psh(int p) {
for(int s=h;s>0;s--) {
int i = p>>s;
if(lz[i] != 0) {
ap(i<<1,lz[i]);
ap(i<<1|1,lz[i]);
lz[i] = 0;
}
}
}
public:
ST(int n_) {
n = n_;
st.assign(2*n,0);
lz.assign(n,0);
}
void reset(ll cons) {
lz.assign(n,0);
for(int i=0;i<n;i++) {
st[i+n] = -cons*i;
}
for(int i=n-1;i>0;i--) {
st[i] = max(st[i<<1],st[i<<1|1]);
}
}
void up(int l, int r, ll val) {
if(l >= r) {return;}
l += n;r += n;
int li = l,ri = r;
for(;l<r;l>>=1,r>>=1) {
if(l&1) {ap(l,val);l++;}
if(r&1) {--r;ap(r,val);}
}
build(li);build(ri-1);
}
ll get(int l, int r) {
l += n;r += n;
psh(l);psh(r-1);
ll res = STV;
for(;l<r;l>>=1,r>>=1) {
if(l&1) {res = max(res,st[l]);l++;}
if(r&1) {--r;res = max(res,st[r]);}
}
return res;
}
};
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
vector<ii> wa;
for(int i=0;i<T;i++) {
wa.emplace_back(W[i],S[i]);
}
sort(X,X+A);
sort(Y,Y+B);
sort(wa.begin(),wa.end());
for(int i=T-1;i>=0;i--) {
int wol = upper_bound(X,X+A,wa[i].first)-X;
int sol = upper_bound(Y,Y+B,wa[i].second)-Y;
wa[i] = {wol,sol};
}
ST su(B+1);
int st = 1,ed = T;
int ls = -1;
while(st <= ed) {
int m = (st+ed)/2;
bool poss = true;
su.reset(m);
int bt = A;
for(int i=T-1;i>=0;i--) {
if(!poss) {break;}
while(bt > wa[i].first) {
if(su.get(0,B+1) > 0) {
poss = false;break;
}
su.up(0,B+1,-m);
bt--;
}
if(!poss) {break;}
int bu = B-wa[i].second;
su.up(bu,B+1,1);
}
if(su.get(0,B+1) > 0) {
poss = false;
}
if(poss) {
ls = m;
ed = m-1;
} else {
st = m+1;
}
}
return ls;
}
