#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>v;
vector<int>x,y;
int a,b,t;
int can(int m){
//cerr<<"m:"<<m<<"\n";
multiset<pair<int,int>>ms;
int cur=0;
for(int i=0;i<a;i++){
//cerr<<"doing weak:"<<x[i]<<"\n";
while(cur<t&&v[cur].first<x[i])ms.insert({v[cur].second,v[cur].first}),cur++;
for(int j=0;j<m&&(!ms.empty());j++){
//cerr<<"erase:"<<prev(ms.end())->first<<" "<<prev(ms.end())->second<<"\n";
ms.erase(prev(ms.end()));
}
}
while(cur<t)ms.insert({v[cur].second,v[cur].first}),cur++;
vector<pair<int,int>>v;
for(auto x:ms)v.push_back(x);
reverse(v.begin(),v.end());
cur=0;
int can=1;
for(int i=0;i<b;i++){
int cnt=0;
while(cnt<m&&cur<v.size()){
if(v[cur].first>=y[i]){
//cerr<<"left:"<<y[i]<<" "<<v[cur].first<<"\n";
can=0;
}
cnt++;
cur++;
}
}
if(cur!=v.size())can=0;
return can;
}
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<T;i++)v.push_back({W[i],S[i]});
sort(v.begin(),v.end());
for(int i=0;i<A;i++)x.push_back(X[i]);
for(int i=0;i<B;i++)y.push_back(Y[i]);
sort(x.begin(),x.end());
sort(y.begin(),y.end());
reverse(y.begin(),y.end());
int st=0,en=2e6,ans=-1;
while(st<=en){
int m=(st+en)/2;
if(can(m)){
en=m-1;
ans=m;
}else{
st=m+1;
}
}
return ans;
}
