#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
struct node {
int id,x,y;
node(int _id = 0,int _x = 0,int _y = 0) {
id = _id; x = _x; y = _y;
}
};
int n,m,k;
int a[50005], b[50005];
bool ok[1000005];
node p[1000005];
map<int,int> mp;
bool cmpx(node x,node y) {
return x.x>y.x;
}
bool cmpy(node x,node y) {
return x.y>y.y;
}
bool check(int cnt) {
int i;
map<int,int>::iterator it;
memset(ok,0,sizeof(ok));
mp.clear();
for(i=0;i<n;i++) mp[a[i]] += cnt;
sort(&p[0],&p[k],cmpy);
for(i=0;i<k;i++) {
it = mp.upper_bound(p[i].x);
if(it==mp.end()) continue;
it->second--;
if(it->second==0) mp.erase(it);
ok[p[i].id] = 1;
}
mp.clear();
for(i=0;i<m;i++) mp[b[i]] += cnt;
sort(&p[0],&p[k],cmpx);
for(i=0;i<k;i++) {
if(ok[p[i].id]) continue;
it = mp.upper_bound(p[i].y);
if(it==mp.end()) continue;
it->second--;
if(it->second==0) mp.erase(it);
ok[p[i].id] = 1;
}
for(i=0;i<k;i++) if(!ok[i]) return 0;
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i,l,r,mid,ans;
n = A; m = B; k = T;
for(i=0;i<n;i++) a[i] = X[i];
for(i=0;i<m;i++) b[i] = Y[i];
for(i=0;i<k;i++) p[i] = node(i,W[i],S[i]);
l = 0; r = k; ans = -1;
while(l<=r) {
mid = (l+r)/2;
if(check(mid)) {
ans = mid;
r = mid-1;
}
else l = mid+1;
}
return ans;
}
