#include "robots.h"
#include <queue>
#include <algorithm>
using namespace std;

#define MAXT 1000006
#define MAXN 50004
typedef pair<int,int> pii;

static int A,B,T,X[MAXN],Y[MAXN];
static struct TOY{
    int w,s;
    bool operator < (const TOY &ot)const{
        return w < ot.w;
    }
} toy[MAXT];
static priority_queue<pii> que;
static int order[MAXT],chk[MAXT];

bool cmp_s(int a,int b){ return toy[a].s<toy[b].s; }

int check(int m)
{
    int i,j,k;
    for (i=1;i<=T;i++) chk[i] = 0;
    while (!que.empty()) que.pop();
    for (i=k=1;i<=A;i++){
        while (k <= T && toy[k].w < X[i]){
            que.push(pii(toy[k].s,k));
            k++;
        }
        for (j=0;j<m&&!que.empty();j++){
            chk[que.top().second] = 1;
            que.pop();
        }
    }
    for (i=k=1;i<=B;i++){
        int cnt=0;
        while (k <= T && toy[order[k]].s < Y[i] && cnt < m){
            if (!chk[order[k]]) cnt++, chk[order[k]] = 1;
            k++;
        }
    }
    for (i=1;i<=T;i++) if (!chk[i]) return 0;
    return 1;
}

int putaway(int a,int b,int t,int x[],int y[],int W[],int S[])
{
    int i,s,e,m,ans=-1;
    A = a, B = b, T = t;
    for (i=1;i<=A;i++) X[i] = x[i-1];
    for (i=1;i<=B;i++) Y[i] = y[i-1];
    for (i=1;i<=T;i++) toy[i].w = W[i-1], toy[i].s = S[i-1], order[i] = i;
    sort(X+1,X+A+1), sort(Y+1,Y+B+1);
    sort(toy+1,toy+T+1); sort(order+1,order+T+1,cmp_s);
    s = 1, e = T;
    while (s <= e){
        m = (s+e)>>1;
        if (check(m)) e = m-1, ans = m;
        else s = m+1;
    }
    return ans;
}