#include <bits/stdc++.h>
#include "robots.h"
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e6+10;
int n, m, t;
int x[maxn], y[maxn];
pii toy[maxn];
bool mark[maxn];
set<pii> st[maxn];
bool ok(int k)
{
for (int i = 1; i <= max(n, t); i++)
st[i].clear(), mark[i] = 0;
int ptr = n;
int tot = 0;
for (int i = t; i >= 1; i--)
{
if (st[ptr].size() == k) ptr--;
if (ptr == 0) break;
if (x[ptr] < toy[i].ff) continue;
mark[i] = 1;
++tot;
st[ptr].insert({toy[i].ss, i});
}
priority_queue<pii> pq;
multiset<pii> candidatos;
for (int i = 1; i <= t; i++)
if (!mark[i])
pq.push({toy[i].ss, i});
for (int i = 1; i <= n; i++)
candidatos.insert({x[i], i});
while (!pq.empty())
{
int i = pq.top().ss; pq.pop();
auto it = candidatos.lower_bound({toy[i].ff, 0});
if (it == candidatos.end()) continue;
int j = it->ss;
if (st[j].begin()->ff >= toy[i].ss)
{
candidatos.erase({x[j], j});
pq.push({toy[i].ss, i});
continue;
}
if (st[j].size() == k)
{
mark[st[j].begin()->ss] = 0;
pq.push(*st[j].begin());
st[j].erase(st[j].begin());
}
mark[i] = 1;
st[j].insert({toy[i].ss, i});
}
vector<int> v;
for (int i = 1; i <= t; i++)
if (!mark[i])
v.push_back(toy[i].ss);
sort(v.begin(), v.end());
ptr = m;
int qtd = 0;
for (int i = v.size()-1; i >= 0; i--)
{
if (qtd == k) ptr--, qtd = 0;
if (ptr == 0 || y[ptr] < v[i]) return 0;
qtd++;
}
return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
n = A, m = B, t = T;
for (int i = 0; i < n; i++)
x[i+1] = X[i]-1;
for (int i = 0; i < m; i++)
y[i+1] = Y[i]-1;
for (int i = 0; i < t; i++)
toy[i+1] = {W[i], S[i]};
sort(x+1, x+n+1); sort(y+1, y+m+1); sort(toy+1, toy+t+1);
int ini = 1, fim = t, ans = -1;
while (ini <= fim)
{
int mid = (ini+fim)>>1;
if (ok(mid)) ans = mid, fim = mid-1;
else ini = mid+1;
}
return ans;
}
