#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define all(x) (x).begin() , (x).end()
#define lc id << 1
#define rc lc | 1
const int MAXN = 1e5 + 100;
int n , lz[MAXN << 2] , psX[MAXN] , psY[MAXN];
ll seg[MAXN << 2];
vector<int> compressX = {-1} , compressY = {-1} , vec[MAXN];
void build(int k , int id = 1 , int l = 0 , int r = MAXN){
lz[id] = 0;
if(r - l == 1){
seg[id] = 1ll * k * psY[l];
return;
}
int mid = l + r >> 1;
build(k , lc , l , mid);
build(k , rc , mid , r);
seg[id] = min(seg[lc] , seg[rc]);
}
void shift(int id){
seg[lc] += lz[id]; lz[lc] += lz[id];
seg[rc] += lz[id]; lz[rc] += lz[id];
lz[id] = 0;
}
void add(int ql , int qr , int x , int id = 1 , int l = 0 , int r = MAXN){
if(qr <= l || r <= ql) return;
if(ql <= l && r <= qr){
lz[id] += x;
seg[id] += x;
return;
}
shift(id);
int mid = l + r >> 1;
add(ql , qr , x , lc , l , mid);
add(ql , qr , x , rc , mid , r);
seg[id] = min(seg[lc] , seg[rc]);
}
int check(int k){
build(k);
for(int i = MAXN - 1 ; i >= 0 ; i--){
for(int j : vec[i]){
add(0 , j + 1 , -1);
// cout << "new " << i << ' ' << j << endl;
}
// cout << "check " << i << ' ' << seg[1] << ' ' << valX[i] << ' ' << valY[i] << endl;
if(seg[1] + 1ll * k * psX[i] < 0) return 0;
}
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++){
// compressX.push_back(W[i]);
// compressY.push_back(S[i]);
}
for(int i = 0 ; i < A ; i++){
compressX.push_back(X[i] - 1);
compressX.push_back(X[i]);
}
for(int i = 0 ; i < B ; i++){
compressY.push_back(Y[i] - 1);
compressY.push_back(Y[i]);
}
sort(all(compressX)); compressX.resize(unique(all(compressX)) - compressX.begin());
sort(all(compressY)); compressY.resize(unique(all(compressY)) - compressY.begin());
for(int i = 0 ; i < T ; i++){
W[i] = lower_bound(all(compressX) , W[i]) - compressX.begin();
S[i] = lower_bound(all(compressY) , S[i]) - compressY.begin();
// cout << W[i] << ' ' << S[i] << endl;
vec[W[i]].push_back(S[i]);
}
for(int i = 0 ; i < A ; i++){
X[i] = lower_bound(all(compressX) , X[i]) - compressX.begin();
// cout << X[i] << endl;
// if(X[i] == 0) return 0;
psX[X[i] - 1]++;
}
// cout << endl;
for(int i = 0 ; i < B ; i++){
Y[i] = lower_bound(all(compressY) , Y[i]) - compressY.begin();
// cout << Y[i] << endl;
// if(Y[i] == 0) return 0;
psY[Y[i] - 1]++;
}
for(int i = MAXN - 2 ; i >= 0 ; i--){
psX[i] += psX[i + 1];
psY[i] += psY[i + 1];
}
int l = 0 , r = MAXN * 10;
while(r - l > 1){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid;
}
return (r == MAXN * 10 ? -1 : r);
}
