//
// Created by adavy on 8/6/2023.
//
//
// Created by adavy on 3/23/2023.
//
//
// Created by adavy on 2/12/2023.
//
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
// pairs
#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
#include "robots.h"
bool doesWork(int time, int A, int B, int T, int X[], int Y[], int W[], int S[]){
// Weak robots: A,X,W
// Small robots: B,Y,S
// We will do first weak robots then small robots.
int canLiftPointer = 0;
// sort the robots
sort(X,X+A);
sort(Y,Y+B,greater<int>());
// SORT THE TOYS... BY WEIGHT!!!
vii toys;
F0R(i,T){
toys.pb({W[i],S[i]});
}
sort(all(toys));
F0R(i,T){
W[i] = toys[i].f;
S[i] = toys[i].s;
}
priority_queue<int> toysRankedBySize;
F0R(i, A){ // WEAK ROBOTS
int weightLimit = lower_bound(W,W+T,X[i])-W;
while (canLiftPointer < weightLimit){
toysRankedBySize.push(S[canLiftPointer]);
canLiftPointer++;
}
F0R(_, time){
if (toysRankedBySize.empty()) break;
toysRankedBySize.pop();
}
}
while (canLiftPointer < T){
toysRankedBySize.push(S[canLiftPointer]);
canLiftPointer++;
}
// SMALL ROBOTS
F0R(i, B){
F0R(_, time){
if (toysRankedBySize.empty()){
return 1;
}
if (toysRankedBySize.top() >= Y[i]) {
return 0;
}
toysRankedBySize.pop();
}
}
if (toysRankedBySize.empty()){
return 1;
}
return 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
ll lb = 0;
ll ub = T+8;
while (lb<ub){
int mid = lb + (ub-lb)/2;
if (doesWork(mid,A,B,T,X,Y,W,S)) {
ub = mid;
}
else lb = mid+1;
}
if (ub==T+8) return -1;
else return lb;
}
/*
#include <stdio.h>
#include <stdlib.h>
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_A 50000
#define MAX_B 50000
#define MAX_T 500000
static int X[MAX_A];
static int Y[MAX_B];
static int W[MAX_T];
static int S[MAX_T];
int main() {
int A, B, T, i;
int res;
FILE *f = fopen("robots.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d", &A);
if (res != 1)
fail("Failed to read A from input file.");
if (A < 0 || A > MAX_A)
fail("A is out of bounds.");
res = fscanf(f, "%d", &B);
if (res != 1)
fail("Failed to read B from input file.");
if (B < 0 || B > MAX_B)
fail("B is out of bounds.");
res = fscanf(f, "%d", &T);
if (res != 1)
fail("Failed to read T from input file.");
if (T < 1 || T > MAX_T)
fail("T is out of bounds.");
for (i = 0; i < A; i++) {
res = fscanf(f, "%d", &X[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < B; i++) {
res = fscanf(f, "%d", &Y[i]);
if (res != 1)
fail("Failed to read data from input file.");
}
for (i = 0; i < T; i++) {
res = fscanf(f, "%d%d", &W[i], &S[i]);
if (res != 2)
fail("Failed to read data from input file.");
}
fclose(f);
int answer = putaway(A, B, T, X, Y, W, S);
printf("%d\n", answer);
return 0;
}
*/
