#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9 + 10;
bool check(int X[], int A, int W[], int T, int k) {
int cur = 0;
for(int i = 0; i < T; i += k) {
int end = min(T, i + k);
for(int j = i; j < end; j++)
if(X[cur] <= W[j]) return false;
cur++;
}
return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
if(A == 0) {
swap(A, B);
swap(X, Y);
swap(W, S);
}
if(B == 0) {
sort(X, X + A);
reverse(X, X + A);
sort(W, W + T);
reverse(W, W + T);
if(!check(X, A, W, T, T)) return -1;
int lo = 0, hi = T;
while(lo + 1 < hi) {
int mid = (lo + hi) >> 1;
if(check(X, A, W, T, mid)) hi = mid;
else lo = mid;
}
return hi;
} else {
sort(X, X + A);
sort(Y, Y + B);
vector<vector<vector<int>>> dp(A + 1, vector<vector<int>>(B + 1, vector<int>(T + 1, INF)));
for(int i = 0; i <= A; i++)
for(int j = 0; j <= B; j++)
dp[i][j][0] = 0;
vector<vector<int>> acum(A + 1, vector<int>(B + 1, 0));
for(int i = 0; i <= A; i++)
for(int j = 0; j <= B; j++) {
int best_a = 0, best_b = 0;
if(i) best_a = X[i - 1];
if(j) best_b = Y[j - 1];
for(int k = 0; k < T; k++)
if(W[k] < best_a and S[k] < best_b)
acum[i][j]++;
}
if(acum[A][B] < T) return -1;
for(int i = 1; i <= A; i++)
for(int j = 1; j <= B; j++)
for(int k = 1; k <= acum[A][B]; k++) {
for(int s = 0; s < k; s++) {
dp[i][j][k] = min(dp[i][j][k], max(dp[i - 1][j][s], k - s));
dp[i][j][k] = min(dp[i][j][k], max(dp[i][j - 1][s], k - s));
}
}
return dp[A][B][T];
}
}
