#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int A, B, T, X[500000], Y[500000];
pair<int,int> Z[2000000];
int sz=1;
int t[8000000+7];
void get_input(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[]){
A=_A;
B=_B;
T=_T;
vector<int> weights, sizes;
for(int i=0;i<A;i++)weights.push_back(_X[i]);
for(int i=0;i<B;i++)sizes.push_back(_Y[i]);
for(int i=0;i<T;i++)weights.push_back(_W[i]);
for(int i=0;i<T;i++)sizes.push_back(_S[i]);
sort(weights.begin(),weights.end());
sort(sizes.begin(),sizes.end());
map<int,int> msizes,mweights;
int cntw=1,cnts=1;
for(int w : weights){
if(!mweights.count(w))mweights[w]=cntw++;
}
for(int s : sizes){
if(!msizes.count(s))msizes[s]=cnts++;
}
for(int i=0;i<A;i++)X[i]=mweights[_X[i]];
for(int i=0;i<B;i++)Y[i]=msizes[_Y[i]];
for(int i=0;i<T;i++)Z[i]={mweights[_W[i]],msizes[_S[i]]};
sort(Z,Z+T);
sort(X,X+A);
sort(Y,Y+B);
// for(int i=0;i<A;i++)cout << X[i] << ' ';
// cout << '\n';
// for(int i=0;i<B;i++)cout << Y[i] << ' ';
// cout << '\n';
// for(int i=0;i<T;i++)cout <<'(' << Z[i].first << ' ' << Z[i].second << ") ";
// cout << '\n';
while(sz<T)sz<<=1;
}
void build(int v, int tl, int tr, vector<int>& a){
if(tl==tr)t[v]=a[v-sz];
else{
int mid=(tl+tr)/2;
build(2*v, tl, mid,a);
build(2*v+1,mid+1, tr, a);
t[v]=min(t[v*2],t[v*2+1]);
}
}
void update(int k, int val){
k+=sz-1;
t[k]=val;
for(k>>=1;k>0;k>>=1)t[k]=min(t[k*2],t[k*2+1]);
}
int find(int val){
if(t[1]>=val)return 0;
int v=1;
while(v<sz){
if(t[v*2+1]<val)v=v*2+1;
else v=v*2;
}
return v-sz+1;
}
bool check(int d){
vector<int> temp(sz,INT32_MAX);
for(int i=0;i<T;i++)temp[i]=Z[i].second;
build(1,1,sz,temp);
for(int i=0;i<B;i++){
for(int j=0;j<d;j++){
int index=find(Y[i]);
if(!index)break;
update(index,INT32_MAX);
}
}
vector<int> rest;
for(int i=0;i<T;i++){
if(t[i+sz]!=INT32_MAX){
rest.push_back(Z[i].first);
}
}
sort(rest.begin(),rest.end());
int ptr=0;
for(int i=0;i<A;i++){
if(ptr==rest.size())break;
for(int j=0;j<d;j++){
if(ptr==rest.size())break;
if(X[i]>rest[ptr])ptr++;
else break;
}
}
if(ptr==rest.size())return 1;
else return 0;
// for(int i=0;i<A;i++)cout << X[i] << ' ';
// cout << '\n';
// for(int i=0;i<B;i++)cout << Y[i] << ' ';
// cout << '\n';
// for(int i=0;i<T;i++)cout <<'(' << Z[i].first << ' ' << Z[i].second << ") ";
// cout << '\n';
}
int putaway(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[]) {
get_input(_A, _B, _T, _X, _Y, _W, _S);
int lo=1, hi=T;
if(!check(hi))return -1;
else if(check(lo))return lo;
while(lo<hi-1){
int mid=(lo+hi)/2;
if(check(mid))hi=mid;
else lo=mid;
}
return hi;
}
