#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
const int MAXT = 1e6+2;
vector<pair<int,int>> T;
int ex[MAXT];
multiset<pair<int,int>> at, bt;
bool check(int a, int b, int t, int X[], int Y[], int cp) {
for (int i=0; i<t; i++) ex[i] = 1;
for (int i=0; i<b; i++) bt.insert({Y[i], cp});
for (int i=0; i<t; i++) {
auto it = bt.lower_bound({T[i].second, 1});
if (it == bt.end()) continue;
pair<int,int> q = *it;
bt.erase(it); q.second--; if (q.second) bt.insert(q);
ex[i] = 0;
}
for (int i=0; i<a; i++) at.insert({X[i], cp});
for (int i=0; i<t; i++) {
if (!ex[i]) continue;
auto it = at.lower_bound({T[i].first, 1});
if (it == at.end()) return 0;
pair<int,int> q = *it;
at.erase(it); q.second--; if (q.second) at.insert(q);
}
return 1;
}
int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]){
for (int i=0; i<t; i++) W[i]++;
for (int i=0; i<t; i++) S[i]++;
sort(X, X+a); sort(Y, Y+b);
for (int i = 0; i < t; i++) T.push_back(make_pair(W[i],S[i]));
sort(T.begin(),T.end(), greater<pair<int,int>>());
int l = 1, r = t+1;
while (l<r) {
at.clear(); bt.clear();
int m = (l+r)/2;
if (check(a,b,t,X,Y,m)) r = m;
else l = m+1;
}
if (l==t+1) return -1; else return l;
}
