#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int a, b, t, x[50005], y[50005], w[1000005], s[1000005];
pair <int, int> w1[1000005], s1[1000001];
int used[1000005];
bool check(int mid)
{
for(int i = 1; i <= t; i++)
used[i] = 0;
priority_queue<pair<int,int>> pq;
int pos = 0;
for(int i = 1; i <= a; i++)
{
while(pos < t && w1[pos + 1].first < x[i])
{
pos++;
pq.push({s[w1[pos].second], w1[pos].second});
}
int cnt = 0;
while(!pq.empty() && cnt < mid)
{
auto p = pq.top(); pq.pop();
if(used[p.second]) continue;
used[p.second] = 1;
cnt++;
}
}
while(!pq.empty()) pq.pop();
pos = 0;
for(int i = 1; i <= b; i++)
{
while(pos < t && s1[pos + 1].first < y[i])
{
pos++;
if(!used[s1[pos].second])
pq.push({w[s1[pos].second], s1[pos].second});
}
int cnt = 0;
while(!pq.empty() && cnt < mid)
{
auto p = pq.top(); pq.pop();
if(used[p.second]) continue;
used[p.second] = 1;
cnt++;
}
}
for(int i = 1; i <= t; i++)
{
if(!used[i]) return false;
}
return true;
}
int bin_search()
{
int l = 1, r = t;
while(l <= r)
{
int mid = (l+r)/2;
if(check(mid))r = mid-1;
else l = mid+1;
}
if(l > t)return -1;
return l;
}
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 < a; i++)
x[i+1] = X[i];
for(int i = 0; i < b; i++)
y[i+1] = Y[i];
for(int i = 0; i < t; i++)
{
w[i+1] = W[i];
s[i+1] = S[i];
w1[i+1] = {w[i+1], i+1};
s1[i+1] = {s[i+1], i+1};
}
sort(w1+1, w1+t+1);
sort(s1+1, s1+t+1);
sort(x+1, x+a+1);
sort(y+1, y+b+1);
return bin_search();
}
