#include<bits/stdc++.h>
#define ll long long
#define ld long double
#include "robots.h"
using namespace std;
// X weight Y size
int a,b,t,X[50001],Y[50001],W[1000001],S[1000001],mxW,mxS , flag = 1,kt[1000000][2];
map<int,int> mp;
ll sufa[50001],sufb[50001];
ld mxa,mxb;
vector<int> f,ds;
void count_max() {
for (int i = 0; i < a; i++) mxW = max (mxW,X[i]);
for (int i = 0; i < b; i++) mxS = max (mxS,Y[i]);
for (int i = 0; i < t; i++)
if (W[i] >= mxW && S[i] >= mxS) flag = 0;
}
int case1() {
if (a == 0) {
if (Y[1] > S[1] && Y[0] > S[0]) return 1;
return 2;
}
if (b == 0) {
if (X[1] > W[1] && X[0] > W[0]) return 1;
return 2;
}
if ((X[0] > W[0] && Y[0] > S[1] ) || (X[0] > W[1] && Y[0] > S[0]) )
return 1;
return 0;
}
int case2() {
set < pair<int,int> > s;
int cnt = 0;
for (int i = 0; i < t; i ++) s.insert ({W[i],cnt++});
set<pair<int,int> > g;
vector<int> v;
for (int i = 0; i < a; i++) v.push_back(X[i]);
int timer = 0;
while (!s.empty()) {
timer++;
for (int j = 0,i; j < v.size() && s.size(); j++) {
i = v[j];
auto it = s.lower_bound({i,0});
if (it == s.begin()){
if (j != v.size() - 1)
swap(v[v.size() - 1],v[j]);
v.pop_back();
j--;
}
else {
it--;
s.erase(it);
}
}
}
return timer;
}
int bad[100000];
int case3() {
vector<int> va,vb;
for (int i = 0; i < a; i++) va.push_back(X[i]);
for (int i = 0; i < b; i++) vb.push_back(X[i]);
int timer = 0;
bool bigflag = 1;
while(bigflag) {
bigflag = 0;
for (int j = 0; j < a; j++) {
int i = X[j];
int in;
bool flag = 0;
int maxa = 0, maxb= 0;
for (int f = 0; f < t; f++) {
if (!bad[f]) {
if (W[f] < i) maxa = max(maxa,W[f]),maxb = max(maxb,S[f]),in = f,flag = 1,bigflag = 1;
}
}
if (!flag) continue;
bad[in] = 1;
if (mxa > mxb) {
for (int i = 0; i < a; i++)
if (X[i] <= maxa) sufa[i] --;
for (int i = 0;i < t; i++) if (!bad[i] && maxa == W[i]) {bad[i] = 1;break;}
}
else {
for (int i = 0; i < b; i++)
if (Y[i] <= maxb) sufb[i] --;
for (int i = 0;i < t; i++) if (!bad[i] && maxb == S[i]) {bad[i] = 1;break;}
}
mxa = mxb= 0;
for (int i = 0; i < a; i++) {
mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
}
for (int i = 0; i < b; i++) {
mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
}
}
for (int j = 0; j < b; j++) { int maxa = 0, maxb= 0;
int i = Y[j];
int in;
bool flag = 0;
for (int f = 0; f < t; f++) {
if (!bad[f]) {
if (S[f] < i) maxa = max(maxa,W[f]),maxb = max(maxb,S[f]),in = f,flag = 1,bigflag = 1;
}
}
if (!flag) continue;
if (mxa > mxb) {
for (int i = 0; i < a; i++)
if (X[i] <= maxa) sufa[i] --;
for (int i = 0;i < t; i++) if (!bad[i] && maxa == W[i]) {bad[i] = 1;break;}
}
else {
for (int i = 0; i < b; i++)
if (Y[i] <= maxb) sufb[i] --;
for (int i = 0;i < t; i++) if (!bad[i] && maxb == S[i]) {bad[i] = 1;break;}
} mxa = mxb= 0;
for (int i = 0; i < a; i++) {
mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
}
for (int i = 0; i < b; i++) {
mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
}
}
if (bigflag) timer++;
}
return timer;
}
int putaway(int A1, int B1, int T1, int X1[], int Y1[], int W1[], int S1[]) {
a = A1; b = B1;t = T1;
for (int i = 0; i < a; i++) X[i] = X1[i],f.push_back(X[i]);
for (int i = 0; i < b; i++) Y[i] = Y1[i],f.push_back(Y[i]);
for (int i = 0; i < t; i++) W[i] = W1[i], S[i] = S1[i],f.push_back(W[i]),f.push_back(W[i]);
sort (X, X + a);
sort (Y, Y + b);
int last = INT_MIN;
int cnt = 0;
count_max();
if (!flag) return -1;
if (b == 0) return case2();
for (int i = a-1; i >= 0; i--) {
if (i) sufa[i] = sufa[i+1];
for (int j = 0; j < t; j++)
if (W[j] >= X[i] && !kt[j][0]) sufa[i]++,kt[j][0] = 0;
}
for (int i = b - 1; i >= 0; i--) {
if (i) sufb[i] = sufb[i+1];
for (int j = 0; j < t; j++)
if (S[j] >= Y[i] && !kt[j][0]) sufb[i]++,kt[j][1] = 1;
}
for (int i = 0; i < a; i++) {
mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
}
for (int i = 0; i < b; i++) {
mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
}
if (t == 2 && a + b == 2) return case1();
return case3();
}
