#include <bits/stdc++.h>
#include "robots.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pi = pair<ll, pair<ll, ll>>;
using ii = pair<int, int>;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
bool cmp(ii A, ii B) {
if(max(A.ff, A.ss) != max(B.ff, B.ss))
return max(A.ff, A.ss) > max(B.ff, B.ss);
return min(A.ff, A.ss) > min(B.ff, B.ss);
}
int st[200001], St[200001];
void update(int v, int l, int r, int p) {
if(l == r) {
st[v]++;
return;
}
int md = (l + r) / 2;
if(p <= md)
update(v * 2, l, md, p);
else update(v * 2 + 1, md + 1, r, p);
st[v] = min(st[v * 2], st[v * 2 + 1]);
}
void Update(int v, int l, int r, int p) {
if(l == r) {
St[v]++;
return;
}
int md = (l + r) / 2;
if(p <= md)
Update(v * 2, l, md, p);
else Update(v * 2 + 1, md + 1, r, p);
St[v] = min(St[v * 2], St[v * 2 + 1]);
}
int query(int v, int l, int r, int lo, int hi, int s) {
if(l > hi || r < lo) return 1e9 + 7;
if(l >= lo && r <= hi)
return (s ? st[v] : St[v]);
return min(query(v * 2, l, (l + r) / 2, lo, hi, s),
query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, s));
}
int get(int v, int l, int r, int lo, int hi, int val) {
if(l > hi || r < lo) return 1e9 + 7;
if(l >= lo && r <= hi && l == r) return l;
if(l >= lo && r <= hi) {
if(st[v * 2] <= val)
return get(v * 2, l, (l + r) / 2, lo, hi, val);
if(st[v * 2 + 1] <= val)
return get(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
return 1e9 + 7;
}
int A = get(v * 2, l, (l + r) / 2, lo, hi, val);
int B = get(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
return min(A, B);
}
int Get(int v, int l, int r, int lo, int hi, int val) {
if(l > hi || r < lo) return 1e9 + 7;
if(l >= lo && r <= hi && l == r) return l;
if(l >= lo && r <= hi) {
if(St[v * 2] <= val)
return Get(v * 2, l, (l + r) / 2, lo, hi, val);
if(St[v * 2 + 1] <= val)
return Get(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
return 1e9 + 7;
}
int A = Get(v * 2, l, (l + r) / 2, lo, hi, val);
int B = Get(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
return min(A, B);
}
int putaway(int A, int B, int T, int X[],
int Y[], int W[], int S[]) {
vector<ii> arr;
for(int l = 0; l < T; l++)
arr.pb({W[l], S[l]});
sort(arr.begin(), arr.end(), cmp);
sort(X, X + A), sort(Y, Y + B);
for(int l = T - 1; l >= 0; l--) {
int U = arr[l].ff, V = arr[l].ss;
if(A > 0 && U < X[A - 1]) continue;
if(B > 0 && V < Y[B - 1]) continue;
return -1;
}
int occ[A + B];
memset(occ, 0, sizeof occ);
for(int l = 0; l < T; l++) {
int U = arr[l].ff, V = arr[l].ss;
int i = lb(X, X + A, U + 1) - X;
int j = lb(Y, Y + B, V + 1) - Y;
int x = query(1, 0, A - 1, i, A - 1, 1);
int y = query(1, 0, B - 1, j, B - 1, 0);
int L = get(1, 0, A - 1, i, A - 1, x);
int R = Get(1, 0, B - 1, j, B - 1, y) + A;
if(i == A) {
occ[R]++; Update(1, 0, B - 1, R - A);
continue;
}
if(j == B) {
occ[L]++; update(1, 0, A - 1, L);
continue;
}
if(occ[R] < occ[L])
Update(1, 0, B - 1, R - A);
else update(1, 0, A - 1, L);
if(occ[R] < occ[L]) swap(L, R);
occ[L]++;
}
int res = 0;
for(int l = 0; l < A + B; l++) {
res = max(res, occ[l]);
}
return res;
}
