#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define konaqua ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define otsuaqua exit(0);
#define debug(x) cout << #x << " => " << x << "\n"
#define all(x) x.begin(), x.end()
#define sp " "
/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
const ll INFF = 1e18 + 5;
const ll INF = 1e10 + 5;
const int MX = 1e6 + 5;
const int MXL = 105;
const int mod = 1e9 + 7;
const double ERROR = 1e-8;
const ld pi = 3.14159265358979323846;
const int set_inf = 0x3f3f3f3f;
int a, b, t;
int l, r, md, ans = -1;
pair <int,int> toys[1000005];
int x[50005], y[50005];
set <pair<int,int>> st;
bool vis[1000005];
int sr[50005], wr[50005], it;
bool check(){
memset(vis, 0, sizeof(vis));
memset(wr, 0, sizeof(wr));
memset(sr, 0, sizeof(sr));
st.clear();
for(int i = 0; i < b; i++)
st.insert({y[i], i});
for(int i = t - 1; i >= 0; i--){
if(st.empty()) break;
auto idx = st.upper_bound({toys[i].se, 1e9 + 7});
if(idx == st.end()) continue;
pair <int,int> p = *idx;
vis[i] = 1;
sr[p.se]++;
if(sr[p.se] >= md) st.erase(idx);
}
it = 0;
for(int i = 0; i < t; i++){
if(vis[i]) continue;
while((toys[i].fi >= x[it] || wr[it] >= md) && it < a) it++;
if(it >= a) break;
vis[i] = 1;
wr[it]++;
}
for(int i = 0; i < t; i++){
if(!vis[i]) return 0;
}
return 1;
}
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++)
toys[i] = make_pair(W[i], S[i]);
sort(toys, toys + t);
for(int i = 0; i < a; i++)
x[i] = X[i];
sort(x, x + a);
for(int i = 0; i < b; i++)
y[i] = Y[i];
sort(y, y + b);
l = 1, r = t;
while(l <= r){
md = (l + r) / 2;
if(check()){
r = md - 1, ans = md;
}
else l = md + 1;
}
return ans;
}
