#include "robots.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
using namespace std;
typedef long long ll;
const int Nmax = 50005, Mmax = 1e6 + 5;
int x[Mmax], y[Mmax], lim1, lim2;
vector<int> v[Nmax];
int cbin(int a[], int n, int x)
{
int st = 0, dr = n - 1;
while(st <= dr)
if(a[mid] > x) st = mid+1;
else dr = mid-1;
return dr + 1;
}
class SegTree
{
ll a[Nmax<<2]; int lazy[Nmax<<2];
public:
void build(int node, int st, int dr, int val)
{
lazy[node] = 0;
if(st == dr)
{
a[node] = - (ll) st * val;
return;
}
build(left_son, st, mid, val);
build(right_son, mid+1, dr, val);
a[node] = max(a[left_son], a[right_son]);
}
void update(int node, int st, int dr, int L)
{
if(L <= st)
{
lazy[node] ++;
return;
}
if(L <= mid) update(left_son, st, mid, L);
update(right_son, mid+1, dr, L);
a[node] = max(a[left_son] + lazy[left_son], a[right_son] + lazy[right_son]);
}
ll query()
{
return a[1] + lazy[1];
}
} aint;
bool check(int D)
{
aint.build(1, 0, lim2, D);
int i;
for(i=0; i<=lim1; ++i)
{
for(auto it : v[i]) aint.update(1, 0, lim2, it);
if((ll) D * i < aint.query()) return 0;
}
return 1;
}
int putaway(int A, int B, int N, int W[], int S[], int X[], int Y[])
{
int i;
sort(W, W+A); reverse(W, W+A);
sort(S, S+B); reverse(S, S+B);
for(i=0; i<N; ++i)
{
x[i] = cbin(W, A, X[i]);
y[i] = cbin(S, B, Y[i]);
if(x[i] == 0 && y[i] == 0) return -1;
}
for(i=0; i<N; ++i)
v[x[i]].push_back(y[i]);
lim1 = A; lim2 = B;
int st = 0, dr = N;
while(st <= dr)
if(check(mid)) dr = mid - 1;
else st = mid+1;
return st;
}
