#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include "robots.h"
using namespace std;
struct toy { int w, s, id; };
bool cmp(const toy& a, const toy& b)
{
return a.s > b.s;
}
bool check(vector<int>& x, vector<int>& y, vector<toy>& v, int t)
// predpokladame ze y su striedene tak, ze prvy je ten najvacsi
{
set<pair<int, int> > m; // vaha ktoru viem zdvihnut, index
for (int i = 0; i < x.size(); i++) m.insert({ x[i], i });
vector<int> fx(x.size(), t), fy(y.size(), t);
int iy = 0;
for (int i = 0; i < v.size(); i++) // predpokladame ze hracky su striedene tym komparatorom vyssie
{
auto it = m.lower_bound({ v[i].w + 1, -1 });
if (it == m.end())
{
while (iy < y.size() && fy[iy] == 0) iy++;
if (iy == y.size() || y[iy] <= v[i].s) return false;
fy[iy]--;
}
else
{
fx[it->second]--;
if (!fx[it->second]) m.erase(it);
}
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
vector<int> x, y; vector<toy> v;
for (int i = 0; i < A; i++) x.push_back(X[i]);
for (int i = 0; i < B; i++) y.push_back(Y[i]);
sort(y.begin(), y.end(), greater<int>());
for (int i = 0; i < T; i++) v.push_back({ W[i], S[i], i });
sort(v.begin(), v.end(), cmp);
int lo = 1, hi = T + 1;
while (lo < hi)
{
int mid = (lo + hi) >> 1;
if (check(x, y, v, mid)) hi = mid;
else lo = mid + 1;
}
return (lo > T ? -1 : lo);
}
