// ~ Be Name Khoda ~ //
#include "robots.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 1e6 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
bool mark[maxn5];
int n, m, t;
priority_queue <int> have[2];
int pt[2], last[2], ind[2], lastlev[2], spen[2][maxn5];
pair <int, int> av[2][maxn5];
inline bool addone(int id, ll lim, int m, int *s){
//cout << "here we have " << id << ' ' << lim << ' ' << last[id] << ' ' << av[id][ind[id]].fi << endl;
if(last[id] + 1 > (av[id][ind[id]].fi) * lim){
int val = have[id].top();
have[id].pop();
for(int i = val; i <= lastlev[id ^ 1]; i++){
spen[id ^ 1][i]++;
if(spen[id ^ 1][i] > i * lim)
return false;
}
last[id ^ 1]++;
have[id].push(m - s[av[id][ind[id]].se]);
spen[id][av[id][ind[id]].fi] = last[id];
lastlev[id] = av[id][ind[id]].fi;
ind[id]++;
}
else{
have[id].push(m - s[av[id][ind[id]].se]);
last[id]++;
spen[id][av[id][ind[id]].fi] = last[id];
lastlev[id] = av[id][ind[id]].fi;
ind[id]++;
}
return true;
}
inline bool check(ll lim, int *x, int *y, int *w, int *s){
//cout << "checkkkkkkkkkkkkkkkkk " << lim << endl;
pt[0] = pt[1] = 0;
for(int i = 0; i < t; i++){
//cout << "hen? " << i << ' ' << w[i] << ' ' << n - w[i] << endl;
av[n - w[i] < m - s[i]][pt[n - w[i] < m - s[i]]++] = {max(n - w[i], m - s[i]), i};
}
sort(av[0], av[0] + pt[0]);
sort(av[1], av[1] + pt[1]);
last[0] = last[1] = 0;
ind[0] = ind[1] = 0;
while(have[0].size())
have[0].pop();
while(have[1].size())
have[1].pop();
lastlev[0] = lastlev[1] = 0;
while(ind[0] < pt[0] || ind[1] < pt[1]){
//cout << "here " << ind[0] << ' ' << pt[0] << ' ' << ind[1] << ' ' << pt[1] << endl;
if(ind[0] < pt[0] && (ind[1] == pt[1] || av[0][ind[0]].fi < av[1][ind[1]].fi)){
if(!addone(0, lim, m, s))
return false;
}
else{
if(!addone(1, lim, n, w))
return false;
}
}
return true;
}
int putaway(int a, int b, int T, int x[], int y[], int w[], int s[]) {
n = a;
m = b;
t = T;
sort(x, x + n);
sort(y, y + m);
for(int i = 0; i < t; i++){
if(w[i] >= x[n - 1] && s[i] >= y[m - 1])
return -1;
w[i] = upper_bound(x, x + n, w[i]) - x;
s[i] = upper_bound(y, y + m, s[i]) - y;
}
int lo = 0, hi = t;
while(hi - lo > 1){
int mid = (hi + lo) >> 1;
if(check(mid, x, y, w, s))
hi = mid;
else
lo = mid;
}
return hi;
}
