#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> toys;
bool check(int a, int b, int t, int x[], int y[], int k, vector<int> l_a){
if(k > t) return true;
vector<int> pre(a + 1), nxt(a + 1), cnt(a + 1, 0);
for(int i=0; i<a; i++) pre[i] = i - 1, nxt[i] = i + 1;
pre[0] = 0, nxt[a] = a;
int l_b = b - 1, cnt_b = 0;
for(int i=0; i<t; i++){
auto [s, w] = toys[i];
while(l_a[i] < a && cnt[l_a[i]] == k) l_a[i] = nxt[l_a[i]];
if(l_a[i] >= a){
if(l_b < 0 || y[l_b] <= s) return false;
cnt_b ++;
if(cnt_b == k) l_b --, cnt_b = 0;
continue;
}
cnt[l_a[i]] ++;
if(cnt[l_a[i]] == k){
nxt[pre[l_a[i]]] = nxt[l_a[i]];
pre[nxt[l_a[i]]] = pre[l_a[i]];
l_a[i] = nxt[l_a[i]];
}
}
return true;
}
int bs(int a, int b, int t, int x[], int y[], vector<int> l_a){
int l = 1, r = t + 1;
while(l < r){
int m = l + (r - l) / 2;
if(check(a, b, t, x, y, m, l_a)) r = m;
else l = m + 1;
}
return r;
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]){
toys.clear();
for(int i=0; i<t; i++) toys.push_back({s[i], w[i]});
sort(toys.rbegin(), toys.rend());
sort(x, x + a);
sort(y, y + b);
vector<int> l_a(t);
for(int i=0; i<t; i++) l_a[i] = upper_bound(x, x + a, toys[i].second) - x;
int ans = bs(a, b, t, x, y, l_a);
return (ans > t ? -1 : ans);
}
