/*input
*/
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
struct toy {
ll s;
ll w;
int i;
};
struct byS {
bool operator()(const toy &a, const toy &b) {
return a.s > b.s or (a.s == b.s and a.i < b.i);
}
};
struct byW {
bool operator()(const toy &a, const toy &b) {
return a.w > b.w or (a.w == b.w and a.i < b.i);
}
};
vl weak, small;
vector<toy> toys;
int Wsz, Ssz;
int N;
bool gali(int S) {
set<toy, byS> taken;
vb been(N, false);
int j = 0;
for (int i = 0; i < Wsz; ++i)
{
while (j < N and toys[j].w < weak[i]) {
taken.insert(toys[j]);
j++;
}
for (int h = 0; h < S && taken.size(); ++h)
{
been[(*taken.begin()).i] = true;
taken.erase(taken.begin());
}
}
taken.clear();
// {
// taken.insert(toys[0]);
// taken.insert(toys[1]);
// printf("t0 = %d, t1 = %d, tkbeg = %d\n", toys[0].s,toys[1].s, (*taken.begin()).s);
// taken.clear();
// }
for (int i = 0; i < N; ++i)
{
if (!been[i])
taken.insert(toys[i]);
}
// printf("S = %d, been: ", S);
// for (auto u : been) printf("%d ", (int)u);
// printf("\n");
for (auto u : small) {
if (taken.empty()) break;
if (u <= (*taken.begin()).s) return false;
for (int i = 0; i < S and taken.size(); ++i)
taken.erase(taken.begin());
}
return taken.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
Wsz = A;
Ssz = B;
N = T;
for (int i = 0; i < A; ++i)
weak.emplace_back(X[i]);
for (int i = 0; i < B; ++i)
small.emplace_back(Y[i]);
toys = vector<toy>(T);
sort(weak.begin(), weak.end());
sort(small.rbegin(), small.rend());
if (!A and !B) return -1;
{
for (int i = 0; i < T; ++i) {
toys[i] = {S[i], W[i], i};
if ((!B or S[i] >= small[0]) and (!A or W[i] >= weak.back())) return -1;
}
}
sort(toys.begin(), toys.end(), [](const toy & a, const toy & b) {
return a.w < b.w;
});
for (int i = 0; i < N; ++i)
toys[i].i = i;
int l = 1;
int r = 1e9;
int m;
while (l < r) {
m = (l + r) / 2;
if (gali(m))
r = m;
else
l = m + 1;
}
return l;
}
