#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 1e6 + 100;
bool used[N];
vector <vector <int>> save;
int re = 0;
void process(int m, vector <int> &x) {
mem(used, 0);
int j = 0;
priority_queue <pair <int, int>> pq;
for (auto t : x) {
while (j < sz(save) && save[j][0] < t) {
pq.push({save[j][1], save[j][2]});
j++;
}
for (int i = 0; i < m; i++) {
if (pq.empty())
break;
auto t = pq.top();
used[t.s] = 1;
re--;
pq.pop();
}
}
}
bool check(int m, vector <int> &y, vector <int> &need) {
int j = 0, cnt = 0, v = 0;
for (auto x : y) {
while (j < sz(need) && need[j] < x) {
j++;
v++;
}
cnt += min(m, v);
v -= min(v, m);
}
return cnt == sz(need);
}
int putaway(int a, int b, int t, int _x[], int _y[], int _w[], int _s[]) {
vector <int> x, y, w, s;
for (int i = 0; i < t; i++) {
w.pb(_w[i]);
s.pb(_s[i]);
}
for (int i = 0; i < a; i++) {
x.pb(_x[i]);
}
for (int i = 0; i < b; i++) {
y.pb(_y[i]);
}
sort(all(x));
sort(all(y));
sort(all(save));
int l = 1, r = t, m, ans = -1;
while (l <= r) {
m = (l + r) / 2;
re = t;
process(m, x);
vector <int> need;
for (int i = 0; i < t; i++) {
if (used[i] == 0) {
need.pb(s[i]);
}
}
sort(all(need));
if (check(m, y, need)) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
