#include "robots.h"
#include <bits/stdc++.h>
#define MP make_pair
#define sc second
#define ad push_back
#define fr first
using namespace std;
const int N = 1e6 + 30;
int n, m, t;
int x[N], y[N], w[N], s[N], col[N], sm[N];
pair<int, int> a[N], b[N];
vector<int> g[N];
bool stg(int k)
{
for (int i = 0; i <= m + 1; i++) sm[i] = 0;
priority_queue <int> q;
int i1 = 0;
for (int i = n; i >= 0; i--)
{
for(auto p : g[i]) q.push(-col[p]);
while(q.size() > i1) sm[-q.top()]++, q.pop();
i1+=k;
i1 = min(t + 1, i1);
}
i1 = 0;
for (int i = m; i >= 0; i--)
{
sm[i] += sm[i+1];
if(sm[i] > i1) return 0;
i1+=k;
i1 = min(t + 1, i1);
}
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 < T; i++)
{
w[i]=W[i];
s[i]=S[i];
a[i]=MP(w[i], i);
b[i]=MP(s[i], i);
}
sort(a, a+t);
sort(b, b+t);
for (int i = 0; i < n; i++) x[i] = X[i];
for (int i = 0; i < m; i++) y[i] = Y[i];
sort(x,x+n);
sort(y,y+m);
int i1 = n;
for (int i = t - 1; i >= 0; i--)
{
while(i1 && x[i1-1] > a[i].fr) i1--;
g[i1].ad(a[i].sc);
}
i1 = m;
for (int i = t - 1; i >= 0; i--)
{
while (i1 && y[i1-1] > b[i].fr) i1--;
col[b[i].sc] = i1;
}
int l = 1, r = t + 1, ans = t + 1;
while(l <= r)
{
int mid = (l + r) / 2;
if(stg(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
if(ans == t+1) return -1;
return ans;
}
