#include "robots.h"
#include <bits/stdc++.h>
const int N = 100100;
const int T = 1100100;
const int INF = 1e9;
using namespace std;
class Heap {
private:
int arr[2 * T];
int sz;
public:
Heap() {
sz = 0;
for (int i = 1; i < T; i++)
arr[i] = INF;
}
void init() {
while (sz) {
arr[sz--] = INF;
}
}
void normalize(int v) {
for (int i = v; i > 1 && arr[i] < arr[i / 2]; i /= 2)
std::swap(arr[i], arr[i / 2]);
}
void push(int x) {
arr[++sz] = x;
normalize(sz);
}
int top() {
return arr[1];
}
void pop() {
arr[1] = INF;
int v = 1;
while (std::min(arr[2 * v], arr[2 * v + 1]) != INF) {
if (arr[2 * v] <= arr[2 * v + 1]) {
std::swap(arr[2 * v], arr[v]);
v = 2 * v;
} else {
std::swap(arr[2 * v + 1], arr[v]);
v = 2 * v + 1;
}
}
std::swap(arr[v], arr[sz]);
sz--;
normalize(v);
}
int size() {
return sz;
}
};
int n, m, t;
int X[T], Y[T];
int W[N], S[N];
vector<int> ord;
Heap pq;
bool check(int k) {
pq.init();
int l = n - 1;
vector<int> rest;
for (int toy : ord) {
while (l >= 0 && W[l] > X[toy])
l--;
pq.push(Y[toy]);
if (1ll * (n - 1 - l) * k < pq.size()) {
rest.push_back(pq.top());
pq.pop();
}
}
// for (int c : rest) cout << c << ' ';
// cout << '\n';
sort(rest.rbegin(), rest.rend());
l = m - 1;
long long cnt = 0;
for (int y : rest) {
while (m >= 0 && S[l] > y) {
cnt += k;
l--;
}
cnt--;
if (cnt < 0) {
return 0;
}
}
return 1;
}
int putaway(int A, int B, int T, int W_inside[], int S_inside[], int X_inside[], int Y_inside[]) {
n = A, m = B, t = T;
for (int i = 0; i < n; i++) W[i] = W_inside[i];
for (int i = 0; i < m; i++) S[i] = S_inside[i];
for (int i = 0; i < t; i++) {
X[i] = X_inside[i];
Y[i] = Y_inside[i];
}
sort(W, W + n);
sort(S, S + m);
ord.resize(t);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
if (X[i] != X[j]) return X[i] > X[j];
return Y[i] > Y[j];
});
int l = 0, r = T + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
if (r == T + 1) return -1;
return r;
}
