#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct toy {
int w, s, id;
bool operator < (const toy &b) const {
if (w!=b.w) return w < b.w;
if (s!=b.s) return s < b.s;
return id < b.id;
}
};
struct thing {
int w, s, id;
bool operator < (const thing &b) const {
return s < b.s;
}
};
int32_t putaway(int32_t n, int32_t m, int32_t k, int32_t x[], int32_t y[], int32_t W[], int32_t S[]) {
sort(x, x+n);
sort(y, y+m);
int mxw = 0, mxs = 0;
if (n > 0) mxw = x[n-1];
if (m > 0) mxs = y[m-1];
toy a[2][k];
for (int i=0;i<k;i++) {
a[0][i] = {W[i], S[i], -1};
a[1][i] = {S[i], W[i], -1};
if (W[i] >= mxw && S[i] >= mxs) return -1;
}
sort(a[0], a[0]+k); sort(a[1], a[1]+k);
for (int i=0;i<k;i++) a[1][i].id = i;
set<toy> s;
for (int i=0;i<k;i++) s.insert(a[1][i]);
for (int i=0;i<k;i++) {
toy bnd = {a[0][i].s, a[0][i].w, -1};
toy cur = *s.lower_bound(bnd);
a[0][i].id = cur.id;
s.erase(cur);
}
int l = 1, r = k;
while (l<r) {
int each = (l+r)/2;
bool used[k];
for (int i=0;i<k;i++) used[i] = false;
priority_queue<thing> pq;
int pt = -1;
for (int i=0;i<n;i++) {
int lim = x[i];
while (pt<k-1 && a[0][pt+1].w < lim) {
pt++;
pq.push({a[0][pt].w, a[0][pt].s, a[0][pt].id});
// cout << "add " << lim << " " << a[0][pt].w << " " << a[0][pt].s << endl;
}
for (int j=0;j<each;j++) {
if (pq.size()==0) break;
thing cur = pq.top();
used[cur.id] = true;
// cout << lim << " " << cur.w << " " << cur.s << endl;
pq.pop();
}
}
pt = -1;
for (int i=0;i<m;i++) {
int lim = y[i];
int cnt = 0;
while (cnt<each && pt<k-1 && a[1][pt+1].w<lim) {
pt++;
if (!used[pt]) cnt++;
used[pt] = true;
}
}
bool ok = true;
for (int i=0;i<k;i++) if (!used[i]) ok = false;
if (ok) r = each;
else l = each + 1;
}
return l;
}
