#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){
int cur = 0;
int rem = t;
priority_queue<pair<int,int>> q;
for(int i=0;i<a;i++){
int cnt=md;
while(cur<t && (vis[toy1[cur].second] || x[i] > toy1[cur].first.first)){
if(!vis[toy1[cur].second])
q.push({toy1[cur].first.second,toy1[cur].second});
cur++;
}
while(q.size() && cnt--){
int cur = q.top().second;
q.pop();
vis[cur]=1;
rem--;
}
}
q = priority_queue<pair<int,int>>();
cur = 0;
for(int i=0;i<b;i++){
int cnt=md;
while(cur<t && (vis[toy2[cur].second] || y[i] > toy2[cur].first.second)){
if(!vis[toy2[cur].second])
q.push({toy2[cur].first.first,toy2[cur].second});
cur++;
}
while(q.size() && cnt--){
int cur = q.top().second;
q.pop();
vis[cur]=1;
rem--;
}
}
return rem == 0;
}
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;
memset(vis,0,sizeof(vis));
}
return ans;
}
