#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
vector<pi> a;
vi b;
set<pi> d;
int x,y,n;
bool solve(int m){
set<pi> c=d;
vi Y(y,m);
int pos=0;
set<int> st;
REP(i,0,x){
while(pos<n&&a[pos].F>=b[i]){
st.insert(a[pos].S);
auto it=c.upper_bound({*st.begin(),y});
if(it==c.end())return 0;
int ps=it->S;
Y[ps]--;
if(Y[ps]==0)c.erase(it);
st.erase(st.begin());
pos++;
}
int cn=m;
while(pos<n&&cn--)st.insert(a[pos++].S);
if(pos==n)break;
}
while(pos<n&&!c.empty()){
st.insert(a[pos].S);
auto it=c.upper_bound({*st.begin(),y});
if(it==c.end())return 0;
int ps=it->S;
Y[ps]--;
if(Y[ps]==0)c.erase(it);
st.erase(st.begin());
pos++;
}
return pos==n;
}
int BS(int l,int r){
if(l==r)return l;
int m=(l+r)/2;
if(solve(m))return BS(l,m);
else return BS(m+1,r);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n=T;x=A;y=B;
a.resize(n);b.resize(x);
REP(i,0,n)a[i]={W[i],S[i]};
REP(i,0,x)b[i]=X[i];
REP(i,0,y)d.insert({Y[i],i});
sort(all(a));sort(all(b));
reverse(all(a));reverse(all(b));
int ans=BS(1,1000001);
if(ans==1000001)return -1;
else return ans;
}
