// ~ 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 <pair<int, int>> have[2];
int pt[2], ind[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;
bool check = true;
for(int i = av[id][ind[id]].fi; i <= max(n, m); i++){
spen[id][i]++;
check &= (spen[id][i] <= lim * i);
}
if(!check){
int val = have[id].top().fi, v = have[id].top().se;
have[id].pop();
for(int i = val; i <= max(n, m); i++){
spen[id ^ 1][i]++;
if(spen[id ^ 1][i] > i * lim)
return false;
}
for(int i = v; i <= max(n, m); i++)
spen[id][i]--;
}
have[id].push({m - s[av[id][ind[id]].se], 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};
}
for(int i = 0; i <= max(n, m); i++)
spen[0][i] = spen[1][i] = 0;
sort(av[0], av[0] + pt[0]);
sort(av[1], av[1] + pt[1]);
ind[0] = ind[1] = 0;
while(have[0].size())
have[0].pop();
while(have[1].size())
have[1].pop();
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;
}
