#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 <ll> vi;
typedef vector <long long> vll;
typedef vector <unsigned long long> vull;
typedef vector <string> vs;
typedef pair <ll, ll> pii;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
const ll maxn = 1e6 + 77;
ll a, b, t;
ll x[maxn];
ll y[maxn];
ll w[maxn];
ll s[maxn];
vector <pii> v1, v2;
ll used[maxn];
bool check(ll yy)
{
memset(used, 0, sizeof(used));
ll p = -1;
priority_queue <pii> q;
for(ll 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(ll j = 1;j <= yy;j++)
{
if(q.empty())break;
used[q.top().Y] = 1;
q.pop();
}
}
priority_queue <pii> q1;
p = -1;
for(ll 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(ll j = 1;j <= yy;j++)
{
if(q1.empty())break;
used[q1.top().Y] = 1;
q1.pop();
}
}
for(ll 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;
ll ma1, ma2;
ma1 = ma2 = 0;
for(ll i = 0;i < a;i++)
{
x[i + 1] = X[i];
ma1 = max(ma1, x[i]);
}
for(ll i = 0;i < b;i++)
{
y[i + 1] = Y[i];
ma2 = max(ma2, y[i]);
}
for(ll i = 1;i <= t;i++)
{
w[i] = W[i - 1];
s[i] = S[i - 1];
//if(w[i] >= ma1 && s[i] >= ma2)return -1;
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);
ll l = 1;
ll r = 2 * t;
ll 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(ll i = 1;i <= a1;i++)
{
cin >> x1[i];
}
for(ll j = 1;j <= b1;j++)
{
cin >> y1[j];
}
for(ll i = 1;i <= t1;i++)
{
cin >> w1[i];
cin >> s1[i];
}
cout << putaway(a1, b1, t1, x1, y1, w1, s1) << endl;
return 0;
}
/**
3 2 10
10 10 9
10 10
4 6
8 5
2 3
7 9
1 8
3 3
8 7
7 6
8 7
5 1
*/
