//by szh
#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
vector <pii> item;
vector <pii> rest;
const int maxn = 1e6+10;
int w[maxn],s[maxn];
int cnt[maxn];
int AA,BB;
bool check(int x) {
// debug(x);
set <pii> robot;
while (!rest.empty()) rest.pop_back();
rep(i,0,BB) robot.insert({s[i],i}),cnt[i] = x;
for (int i=0;i<SZ(item);i++) {
auto it = robot.upper_bound({item[i].se,mod});
if (it == robot.end()) rest.pb(item[i]);
else {
pii cur = *it;
cnt[cur.se]--;
if (cnt[cur.se]==0) robot.erase(cur);
}
}
robot.clear();
rep (i,0,AA) robot.insert({w[i],i}),cnt[i] = x;
for (int i=0;i<SZ(rest);i++) {
auto it = robot.upper_bound({rest[i].fi,mod});
// debug(rest[i].fi);
if (it == robot.end()) return false;
else {
pii cur = *it;
// debug(cur.fi);
cnt[cur.se]--;
if (cnt[cur.se]==0) robot.erase(cur);
}
}
return true;
}
bool cmp (pii a, pii b ) {
if (a.fi==b.fi) return a<b;
else return a.fi>b.fi;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
AA=A,BB=B;
rep(i,0,T) item.pb({W[i],S[i]});
sort(X,X+A);
sort(Y,Y+B);
rep(i,0,A) w[i] = X[i];
rep(i,0,B) s[i] = Y[i];
sort(ALL(item),cmp);
if (!check(T)) return -1;
int l = 1,r = T;
while (l<r) {
int mid=l+r>>1;
if (check(mid)) r = mid;
else l = mid+1;
}
return l;
}
/*
int main() {
int tmp1[] = {5,7};
int tmp2[] = {};
int tmp3[] = {1,7};
int tmp4[] = {};
cout<<putaway(2,0,2, tmp1, tmp2, tmp3,tmp4);
}
*/
