#include "robots.h"
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
using namespace std;
vector<int> w,s;
bool comp(int a,int b){
if(w[a]!=w[b])return w[a]>w[b];
return s[a]>s[b];
}
int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]){
sort(X,X+A);
sort(Y,Y+B);
vector<int>ind;
for(int i = 0;i<T;i++){
ind.push_back(i);s.push_back(S[i]);w.push_back(W[i]);
}
sort(ind.begin(),ind.end(),comp);
int l = 1 , r = 1e6 , ans= -1;
while(l<=r){
int mid=(l+r)/2;
set<pair<int,int>> se,aa,bb;
for(int i = 0;i<A;i++)aa.insert({i,mid});
for(int i = 0;i<B;i++)bb.insert({i,mid});
pair<int,int> p;p.second = 0;
bool ss = 1;
for(int i = 0;i<T;i++){
int toy = ind[i];
p.first = lower_bound(X,X+A,W[toy]+1)-X;
p.second = 0;
auto it = aa.lower_bound(p);
int in = lower_bound(Y,Y+B,S[toy]+1)-Y;
se.insert({in,toy});
if(it!=aa.end()){
pair<int,int>tmp = *it;
aa.erase(it);
tmp.second--;
if(tmp.second){
aa.insert(tmp);
}
}else{
p.first=(*se.begin()).first;
p.second = 0;
auto it2 = bb.lower_bound(p);
if(it2==bb.end()){
ss= 0;
break;
}
pair<int,int>tmp=*it2;
bb.erase(it2);
tmp.second--;
if(tmp.second)bb.insert(tmp);
se.erase(se.begin());
}
}
if(ss)r = mid-1, ans= mid;
else l = mid+1;
}
return ans;
}
/*
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int X[] = {6,2,9};
int Y[] = {4,7};
int W[] = {4,8,2,7,1,5,3,8,7,10};
int S[] = {6,5,3,9,8,1,3,7,6,5};
cout<<putaway(3,2,10,X,Y,W,S)<<endl;
}
*/
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
*/
