#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include "robots.h"
using namespace std;
const int maxn = int(1e6)+5, maxs = int(5e4)+5, inf = int(1e9)+5;
int t, a, b, X[maxs], Y[maxs], undone[maxn];
pair<int, int> A[maxn];
vector<int> guys[maxs];
bool f(int x)
{
int undone = 0;
pair<int, int> ptr = {0, x};
for(int i = 0;i < a;i++)
{
if(int(guys[i].size()) < x)
{
int tmp = x-int(guys[i].size());
undone = max(0, undone-tmp);
}
else
{
for(int j = 0;j < int(guys[i].size())-x;j++)
{
if(ptr.first == b)
{
undone++;
continue;
}
while(ptr.first < b && (guys[i][j] >= Y[ptr.first] || !ptr.second)) ptr.first++, ptr.second = x;
if(ptr.first == b)
{
undone++;
continue;
}
ptr.second--;
}
}
}
for(int j = 0;j < int(guys[a].size());j++)
{
if(ptr.first == b)
{
undone++;
continue;
}
while(ptr.first < b && (guys[a][j] >= Y[ptr.first] || !ptr.second)) ptr.first++, ptr.second = x;
if(ptr.first == b)
{
undone++;
continue;
}
ptr.second--;
}
//cout << x << " " << undone << "\n";
return !undone;
}
int putaway(int _A, int _B, int _T, int _X[], int _Y[], int _W[], int _S[])
{
a = _A, b = _B, t = _T;
for(int i = 0;i < t;i++) A[i] = {_W[i], _S[i]};
for(int i = 0;i < a;i++) X[i] = _X[i];
for(int i = 0;i < b;i++) Y[i] = _Y[i];
sort(A, A+t), sort(X, X+a), sort(Y, Y+b);
int ptr = 0;
for(int i = 0;i < a;i++)
{
while(ptr < t && A[ptr].first < X[i])
{
guys[i].push_back(A[ptr].second);
ptr++;
}
sort(guys[i].begin(), guys[i].end());
}
while(ptr < t)
{
guys[a].push_back(A[ptr].second);
ptr++;
}
sort(guys[a].begin(), guys[a].end());
int L = 1, R = t+1, ans = inf;
while(L <= R)
{
int mid = (L+R)/2;
if(f(mid)) R = mid-1, ans = min(ans, mid);
else L = mid+1;
}
return ((ans > t+1)?-1:ans);
}
