#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int n,na,nb;
bool desc (int a, int b)
{
return a>b;
}
struct ura
{
int a,b,ok;
}v[1000003];
bool cmp (ura a, ura b)
{
return a.b<b.b;
}
int cnta[50003],cntb[50003],nxta[50003],nxtb[50003];
int getnextA(int pz)
{
if(nxta[pz]==pz)
return pz;
return nxta[pz]=getnextA(nxta[pz]);
}
void addToA (int pz, int val)
{
int pzadd=getnextA(v[pz].a);
if(pzadd)
{
v[pz].ok=1;
++cnta[pzadd];
if(cnta[pzadd]==val)
nxta[pzadd]=nxta[pzadd-1];
}
}
int getnextB(int pz)
{
if(nxtb[pz]==pz)
return pz;
return nxtb[pz]=getnextB(nxtb[pz]);
}
void addToB (int pz, int val)
{
int pzadd=getnextB(v[pz].b);
if(pzadd)
{
v[pz].ok=1;
++cntb[pzadd];
if(cntb[pzadd]==val)
nxtb[pzadd]=nxtb[pzadd-1];
}
}
bool verif (int val)
{
for(int i=1;i<=na;++i)
cnta[i]=0,nxta[i]=i;
for(int i=1;i<=nb;++i)
cntb[i]=0,nxtb[i]=i;
for(int i=1;i<=n;++i)
{
v[i].ok=0;
addToA(i,val);
}
for(int i=1;i<=n;++i)
{
if(!v[i].ok)
addToB(i,val);
if(!v[i].ok)
return false;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
n=T;
na=A;
nb=B;
sort(X,X+A,desc);
sort(Y,Y+B,desc);
int ok=1;
for(int i=0;i<T;++i)
{
int k=-1;
int pas=(1<<15);
while(pas)
{
if(k+pas<A && X[k+pas]>W[i])
k+=pas;
pas>>=1;
}
v[i+1].a=k+1;
k=-1;
pas=(1<<15);
while(pas)
{
if(k+pas<B && Y[k+pas]>S[i])
k+=pas;
pas>>=1;
}
v[i+1].b=k+1;
v[i+1].ok=0;
if(v[i+1].a == 0 && v[i+1].b == 0)
return -1;
}
sort(v+1,v+T+1,cmp);
int pas=(1<<19);
int k=0;
while(pas)
{
if(!verif(k+pas))
k+=pas;
pas>>=1;
}
return k+1;
}
/*
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000
static int X[MAX_A];
static int Y[MAX_B];
static int W[MAX_T];
static int S[MAX_T];
int main() {
int A, B, T, i;
int res;
FILE *f = fopen("a.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d", &A);
if (res != 1)
fail("Failed to read A from input file.");
if (A < 0 || A > MAX_A)
fail("A is out of bounds.");
res = fscanf(f, "%d", &B);
if (res != 1)
fail("Failed to read B from input file.");
if (B < 0 || B > MAX_B)
fail("B is out of bounds.");
res = fscanf(f, "%d", &T);
if (res != 1)
fail("Failed to read T from input file.");
if (T < 1 || T > MAX_T)
fail("T is out of bounds.");
for (i = 0; i < A; i++) {
res = fscanf(f, "%d", &X[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < B; i++) {
res = fscanf(f, "%d", &Y[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < T; i++) {
res = fscanf(f, "%d%d", &W[i], &S[i]);
if (res != 2)
fail("Failed to read data from input file.");
}
fclose(f);
int answer = putaway(A, B, T, X, Y, W, S);
printf("%d\n", answer);
return 0;
}*/
