#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 5e4+50;
const ll oo = 1e18;
const ll mod = 1e9+7;
int a,b,t,x[N],y[N];
pair<pair<int,int>,int> toy1[1000010],toy2[1000010];
bool vis[1000010];
bool cmp1(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
return a.first.first < b.first.first || (a.first.first == b.first.first && a.first.second < b.first.second);
}
bool cmp2(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
return a.first.second < b.first.second || (a.first.second == b.first.second && a.first.first < b.first.first);
}
bool check(int md){
for(int i=0;i<t;i++)vis[i]=0;
int cur = t-1;
for(int i=a-1;i>=0;i--){
int cnt=0;
while(cur>=0 && cnt < md){
if(!vis[toy1[cur].second] && x[i] > toy1[cur].first.first){
vis[toy1[cur].second] = 1;
cnt++;
}
cur--;
}
}
cur = t-1;
for(int i=b-1;i>=0;i--){
int cnt=0;
while(cur>=0 && cnt < md){
if(!vis[toy2[cur].second] && y[i] > toy2[cur].first.second){
vis[toy2[cur].second] = 1;
cnt++;
}
cur--;
}
}
for(int i=0;i<t;i++)if(!vis[i])return 0;
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
a=A;
b=B;
t=T;
for(int i=0;i<a;i++)x[i]=X[i];
for(int i=0;i<b;i++)y[i]=Y[i];
for(int i=0;i<t;i++)toy1[i] = toy2[i] = {{W[i],S[i]},i};
sort(toy1, toy1 + t, cmp1);
sort(toy2, toy2 + t, cmp2);
sort(x,x+a);
sort(y,y+b);
int md,lo=0,hi=t,ans=-1;
while(lo <= hi){
md = (lo+hi)/2;
if(check(md)){
hi = md-1;
ans = md;
}else lo = md+1;
}
return ans;
}
