#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
const int maxn = 1e6 + 10;
int a, b, t;
int x[maxn], y[maxn];
struct c
{
int w, s, ind;
};
bool cmp1(c c1, c c2)
{
if(c1.w == c2.w) return c1.s < c2.s;
return c1.w < c2.w;
}
bool cmp2(c c1, c c2)
{
if(c1.s == c2.s) return c1.w < c2.w;
return c1.s < c2.s;
}
c s1[maxn], s2[maxn];
bool check(c c1, c c2)
{
return (c1.s > c2.s && c1.w > c2.w);
}
bool query(int tim)
{
vector<int> taken(t + 1, 0);
priority_queue<pair<int,int>> q;
int p = 1;
for(int i = 1; i <= a; i++)
{
while(p <= t && s1[p].w < x[i])
{
q.push({s1[p].s, s1[p].ind});
p++;
}
int br = 0;
while(!q.empty() && br < tim)
{
taken[q.top().second] = 1;
q.pop();
br++;
}
}
vector<c> rem;
rem.reserve(t);
for(int i = 1; i <= t; i++)
{
if(!taken[s1[i].ind]) rem.push_back(s1[i]);
}
sort(rem.begin(), rem.end(), cmp2);
priority_queue<pair<int,int>> q1;
p = 0;
int n = (int)rem.size();
for(int i = 1; i <= b; i++)
{
while(p < n && rem[p].s < y[i])
{
q1.push({rem[p].w, p});
p++;
}
int br = 0;
while(!q1.empty() && br < tim)
{
q1.pop();
br++;
}
}
return q1.empty() && p == n;
}
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 < a; i++) x[i + 1] = X[i];
for(int i = 0; i < b; i++) y[i + 1] = Y[i];
for(int i = 0; i < t; i++)
{
s1[i + 1] = {W[i], S[i], i + 1};
s2[i + 1] = s1[i + 1];
}
sort(x + 1, x + a + 1);
sort(y + 1, y + b + 1);
sort(s1 + 1, s1 + t + 1, cmp1);
sort(s2 + 1, s2 + t + 1, cmp2);
int mxw = 0, mxs = 0;
if(a > 0) mxw = x[a];
if(b > 0) mxs = y[b];
for(int i = 1; i <= t; i++)
{
if((a == 0 || s1[i].w >= mxw) && (b == 0 || s1[i].s >= mxs))
{
return -1;
}
}
int l = 1, r = t, mid, ans = -1;
while(l <= r)
{
mid = (l + r) / 2;
if(query(mid))
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return ans;
}
