/*
░░░░██████████████████
░░▄███████▀▀▀▀▀▀███████▄
░▐████▀▒mohammad▒▀██████▄
░███▀▒▒▒▒alaa▒▒▒▒▒▒▀█████
░▐██▒▒▒alwrawrah▒▒▒▒▒████▌
░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
░░░░▄██████████████▒▒▐▌
░░░▀███▀▀████▀█████▀▒▌
░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐
*/
#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
typedef long long ll ;
const ll oo = 1e13 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7 ;
pair<int , int > w[1000010] , s[1000010] , mp[1000010] ;
int use[1000010], n , m , t;
//=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
bool cmp(const pair<int , int> i, const pair<int,int> j){
return (i.first != j.first ? i.first < j.first : mp[i.second].second > mp[j.second].second);
}
bool cmp1(const pair<int , int> i, const pair<int,int> j){
return (i.first != j.first ? i.first < j.first : mp[i.second].first > mp[j.second].first);
}
bool cn(int md , int X[] , int Y[]){
set<pair<int,int>> s1;
int idx = 0;
int res = 0;
for(int i = 0 ; i < n ; ++i){
while(idx != t && w[idx].first < X[i]){
int id = w[idx].second;
s1.insert({-mp[id].second , id});
idx++;
}
int q = md ;
while(q-- && s1.size()){
auto it = s1.begin();
int x = it->second ;
s1.erase(s1.begin()) ;
use[x] = 1;
res++;
}
}
s1.clear();
idx = 0 ;
for(int i = 0 ; i < m ; ++i){
while(idx != t && (s[idx].first < Y[i] || use[s[idx].second])){
int id = s[idx].second;
if(!use[id])
s1.insert({-mp[id].first , id});
else
use[id] = 1;
idx++;
}
int q = md ;
while(q-- && s1.size()){
res++;
s1.erase(s1.begin()) ;
}
}
return (res == t);
}
//=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
n = A ;
m = B ;
t = T;
sort(X , X + A) ;
sort(Y , Y + B) ;
for(int i = 0 ; i < T ; ++i){
w[i] = {W[i] , i};
s[i] = {S[i] , i};
mp[i] = {W[i] , S[i]};
}
sort(w , w + T , cmp);
sort(s , s + T , cmp1);
int lo = 0 , hi = T + 1 , ans = -1;
while(lo <= hi){
int md = (lo + hi) / 2 ;
if(cn(md , X , Y)){
hi = md - 1;
ans = md ;
}else{
lo = md + 1;
}
}
return ans;
}
