// In the name of Allah
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 4;
const int maxs = 5e4 + 4;
int n, m1, m2, R;
pii A[maxn]; int A1[maxs], A2[maxs];
int t[4 * maxs];
bool cmp(pii a, pii b) {
if (a.S != b.S) return (a.S < b.S);
else return (a.F > b.F);
}
void build(int v, int tl, int tr) {
if (tr - tl <= 0) return ;
if (tr - tl == 1) {
t[v] = R;
return ;
}
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
t[v] = (t[2 * v + 1] + t[2 * v + 2] >= 1);
}
void add_val(int v, int tl, int tr, int i, int x) {
if (tr - tl <= 0) return ;
if (i >= tr || i < tl) return ;
if (tr - tl == 1) {
t[v] += x;
return ;
}
int mid = (tl + tr) / 2;
add_val(2 * v + 1, tl, mid, i, x); add_val(2 * v + 2, mid, tr, i, x);
t[v] = (t[2 * v + 1] + t[2 * v + 2] >= 1);
}
int get_ind(int v, int tl, int tr, int x) {
if (tr - tl <= 0) return -1;
if (tl >= x || t[v] == 0) return -1;
if (tr - tl == 1) return tl;
int mid = (tl + tr) / 2;
int j = get_ind(2 * v + 2, mid, tr, x);
if (j != -1) return j;
else return get_ind(2 * v + 1, tl, mid, x);
}
bool ok(int valx) {
R = valx;
build(0, 0, m1); pii val = Mp(0, R);
for (int i = 0; i < n; i++) {
int x = A[i].F, y = A[i].S;
int j = get_ind(0, 0, m1, x);
if (j != -1) {
add_val(0, 0, m1, j, -1);
}
else {
if (val.F < y) {
val.S--;
if (val.S == 0) val = Mp(val.F + 1, R);
}
else return 0;
}
}
return 1;
}
int putaway(int Ax, int Bx, int Tx, int X[], int Y[], int W[], int S[]) {
n = Tx; m1 = Ax; m2 = Bx;
for (int i = 0; i < m1; i++) A1[i] = X[i];
for (int i = 0; i < m2; i++) A2[i] = Y[i];
sort(A1, A1 + m1); sort(A2, A2 + m2);
for (int i = 0; i < n; i++) {
int j1 = m1 - (upper_bound(A1, A1 + m1, W[i]) - A1);
int j2 = m2 - (upper_bound(A2, A2 + m2, S[i]) - A2);
A[i] = Mp(j1, j2);
if (j1 == 0 && j2 == 0) return -1;
}
sort(A, A + n, cmp);
int l = 0, r = n + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (ok(mid)) r = mid;
else l = mid;
}
return r;
}
