#include <bits/stdc++.h>
#include "robots.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#define endl '\n'
#define X first
#define Y second
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef vector <long long> vll;
typedef vector <unsigned long long> vull;
typedef vector <string> vs;
typedef pair <int, int> pii;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
const int maxn = 2e5 + 7;
int a, b, t;
int x[maxn];
int y[maxn];
int w[maxn];
int s[maxn];
vector <pii> v1, v2;
int used[maxn];
bool check(int yy)
{
memset(used, 0, sizeof(used));
int p = -1;
priority_queue <pii> q;
for(int i = 1;i <= a;i++)
{
while(p + 1 < t && x[i] > v1[p + 1].X)
{
p++;
if(used[v1[p].Y] == 1)continue;
q.push({s[v1[p].Y], v1[p].Y});
}
for(int j = 1;j <= yy;j++)
{
if(q.empty())break;
used[q.top().Y] = 1;
q.pop();
}
}
priority_queue <pii> q1;
p = -1;
for(int i = 1;i <= b;i++)
{
while(p + 1 < t && y[i] > v2[p + 1].X)
{
p++;
if(used[v2[p].Y] == 1)continue;
q1.push({w[v2[p].Y], v2[p].Y});
}
for(int j = 1;j <= yy;j++)
{
if(q1.empty())break;
used[q1.top().Y] = 1;
q1.pop();
}
}
for(int i = 1;i <= t;i++)
{
if(used[i] == 0)return false;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
a = A;
b = B;
t = T;
int ma1, ma2;
ma1 = ma2 = 0;
for(int i = 1;i <= a;i++)
{
x[i] = X[i];
ma1 = max(ma1, x[i]);
}
for(int i = 1;i <= b;i++)
{
y[i] = Y[i];
ma2 = max(ma2, y[i]);
}
for(int i = 1;i <= t;i++)
{
w[i] = W[i];
s[i] = S[i];
v1.push_back({w[i], i});
v2.push_back({s[i], i});
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
sort(x + 1, x + 1 + a);
sort(y + 1, y + 1 + b);
int l = 1;
int r = 2 * t;
int mid;
while(l <= r)
{
mid = (l + r) / 2;
if(check(mid))r = mid - 1;
else l = mid + 1;
}
if(check(l) == 0)return -1;
else return l;
}
/*int main()
{
int a1, b1, t1;
cin >> a1 >> b1 >> t1;
int x1[maxn];
int y1[maxn];
int w1[maxn];
int s1[maxn];
for(int i = 1;i <= a1;i++)
{
cin >> x1[i];
}
for(int j = 1;j <= b1;j++)
{
cin >> y1[j];
}
for(int i = 1;i <= t1;i++)
{
cin >> w1[i];
cin >> s1[i];
}
cout << putaway(a1, b1, t1, x1, y1, w1, s1) << endl;
return 0;
}*/
