#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};
void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;
template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "["; REP(i, U) out << v[i] << ", "; out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;}
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
struct flow_edge{
int src, dest;
int flow, cap;
int id;
bool operator<(flow_edge &oth){
return src < oth.src;
}
};
struct flow_network{
vector<int> g;
vector<flow_edge> edges;
vector<int> start;
vector<int> end;
vector<int> level;
vector<int> ptr;
vector<int> position;
int s, t;
int n, m = 0;
flow_network(int _n, int _s, int _t) : n(_n), s(_s), t(_t){
level.resize(n);
ptr.resize(n);
start.resize(n, INF);
end.resize(n, -1);
}
void add_edge(int src, int dest, int cap){
edges.pb({src, dest, 0, cap, m});
edges.pb({dest, src, 0, 0, m + 1});
//g[src].pb(m);
//g[dest].pb(m + 1);
m += 2;
}
void build_graph(){
sort(edges.begin(), edges.end());
g.resize(edges.size());
position.resize(n);
REP(i, edges.size()){
g[i] = edges[i].id;
start[edges[i].src] = min(start[edges[i].src], i);
end[edges[i].src] = max(end[edges[i].src], i);
position[edges[i].id] = i;
}
};
bool bfs(){
fill(level.begin(), level.end(), -1);
REP(i, n){
ptr[i] = start[i];
}
queue<int> q;
q.push(s);
level[s] = 0;
while(!q.empty()){
int v = q.front();
q.pop();
FOR(i, start[v], end[v] + 1, 1){
int id = g[i];
auto e = edges[id];
if(e.cap - e.flow < 1) continue;
if(level[e.dest] == -1){
level[e.dest] = level[e.src] + 1;
q.push(e.dest);
}
}
}
return level[t] != -1;
}
int dfs(int v, int pushed){
if(pushed == 0)
return 0;
if(v == t) return pushed;
for(int &cid = ptr[v]; cid < end[v]; ++cid){
int id = g[cid];
auto &e = edges[position[id]];
auto &e2 = edges[position[id^1]];
if(e.cap - e.flow < 1 || level[e.dest] != level[e.src] + 1) continue;
int tr = dfs(e.dest, min(pushed, e.cap - e.flow));
if(tr == 0) continue;
e.flow += tr; e2.flow -= tr;
return tr;
}
return 0;
}
int get_flow(){
int res_flow = 0;
while(true){
if(!bfs())
break;
while(int pushed = dfs(s, INF))
res_flow += pushed;
}
return res_flow;
}
};
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
auto solve_small = [&](){
multiset<int> se;
REP(i, T) se.insert(W[i]);
vector<int> nx;
REP(i, A) nx.pb(X[i]);
if(*se.rbegin() >= *max_element(all(nx)))
return -1;
int ans = 0;
int pp = 0;
sort(all(nx));
while(!se.empty()){
ans++;
int nxt_pp = pp;
FOR(i, pp, nx.size(), 1){
auto it = se.lower_bound(nx[i]);
if(it == se.begin()){
nxt_pp = max(nxt_pp, i + 1);
}
else{
it--; se.erase(it);
}
}
pp = nxt_pp;
}
return ans;
};
if(B == 0)
return solve_small();
auto construct_network = [&](){
flow_network preset(T + 2 * A + 2 * B + 2, T + 2 * A + 2 * B, T + 2 * A + 2 * B + 1);
// [0 ... A) - Acka; [A ... A + B) - bcka
// [A + B ... A + B + T) - hracky
// potom specialne vrcholy, na limit E
vector<int> nx;
REP(i, A) nx.pb(X[i]);
sort(all(nx));
nx.erase(unique(all(nx)), nx.end());
vector<int> toys_sorted(T);
iota(all(toys_sorted), 0);
sort(all(toys_sorted), [&](int lhs, int rhs){
return W[lhs] < W[rhs];
});
int pp = 0;
int curr = A + B + T;
REP(i, nx.size()){
while(pp < T && W[toys_sorted[pp]] < nx[i]){
preset.add_edge(curr, A + B + toys_sorted[pp], 1);
pp++;
}
REP(j, A){
if(X[j] >= nx[i]){
preset.add_edge(j, curr, INF);
}
}
curr++;
}
vector<int> ny;
REP(i, B) ny.pb(Y[i]);
sort(all(ny));
ny.erase(unique(all(ny)), ny.end());
sort(all(toys_sorted), [&](int lhs, int rhs){
return S[lhs] < S[rhs];
});
pp = 0;
REP(i, ny.size()){
while(pp < T && S[toys_sorted[pp]] < ny[i]){
preset.add_edge(curr, A + B + toys_sorted[pp], 1);
pp++;
}
REP(j, B){
if(Y[j] >= ny[i]){
preset.add_edge(A + j, curr, INF);
}
}
curr++;
}
REP(i, T){
preset.add_edge(A + B + i, preset.t, 1);
}
return preset;
};
int l = 0;
int r = 1000005;
int ans = INF;
while(l <= r){
int mid = (l + r) >> 1;
flow_network fn = construct_network();
REP(i, A + B){
fn.add_edge(fn.s, i, mid);
}
fn.build_graph();
int flow = fn.get_flow();
if(flow == T){
ans = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
if(ans == INF)
return -1;
return ans;
}
