#include "robots.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
static const int N = 1'000'010;
static pii toys[N];
bool bintry(int cnt, int a, int b, int t, int x[], int y[], int w[], int s[])
{
multiset<int, greater<int>> by_s;
int i, j;
for (i=0,j=0; i < a; ++i) {
while (j < t && toys[j].first < x[i]) {
by_s.insert(toys[j].second);
++j;
}
for (int _=0; _<cnt && by_s.size(); ++_)
by_s.erase(by_s.begin());
}
for (; j < t; ++j)
by_s.insert(toys[j].second);
for (i=b-1; i>=0; --i) {
if (by_s.size() && *by_s.begin() >= y[i])
return 0;
for (int _=0; _<cnt && by_s.size(); ++_)
by_s.erase(by_s.begin());
}
if (by_s.size())
return 0;
return 1;
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
Loop (i,0,t)
toys[i] = {w[i], s[i]};
sort(toys, toys+t);
sort(x, x+a);
sort(y, y+b);
int l = 0, r = t+1;
while (l < r) {
int m = (l+r)/2;
if (bintry(m, a,b,t,x,y,w,s))
r = m;
else
l = m+1;
}
return l==t+1?-1:l;
}
