#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<double> CMP;
class SpaceWarDiv1 { public:
long long minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount)
{
int M = *max_element(magicalGirlStrength.begin(), magicalGirlStrength.end());
int E = *max_element(enemyStrength.begin(), enemyStrength.end());
if(M<E)
return -1;
sort(magicalGirlStrength.rbegin(), magicalGirlStrength.rend());
vector< pair<int,LL> > e;
for(int i=0; i<enemyStrength.size(); ++i)
e.push_back(make_pair(enemyStrength[i], enemyCount[i]));
sort(e.rbegin(), e.rend());
LL L=0, R=accumulate(enemyCount.begin(), enemyCount.end(), 0LL); // (L,R)
while(R-L>1) {
LL C = (L+R)/2;
(possible(magicalGirlStrength, e, C) ? R : L) = C;
}
return R;
}
bool possible(const vector<int>& m, const vector<pair<int,LL> >& e, LL F)
{
int ei = 0;
LL eC = e[ei].second;
for(int i=0; i<m.size() && ei<e.size(); ++i)
{
if(e[ei].first > m[i])
return false;
for(LL p = F; p; ) {
if(eC > p) {
eC -= p;
p = 0;
}
else {
++ei;
if(ei == e.size())
return true;
p -= eC;
eC = e[ei].second;
}
}
}
return (ei == e.size());
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, SpaceWarDiv1().minimalFatigue(magicalGirlStrength, enemyStrength, enemyCount));}
int main(){
CASE(0)
int magicalGirlStrength_[] = {2, 3, 5};
vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
int enemyStrength_[] = {1, 3, 4};
vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
long long enemyCount_[] = {2, 9, 4};
vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
long long _ = 7LL;
END
CASE(1)
int magicalGirlStrength_[] = {2, 3, 5};
vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
int enemyStrength_[] = {1, 1, 2};
vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
long long enemyCount_[] = {2, 9, 4};
vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
long long _ = 5LL;
END
CASE(2)
int magicalGirlStrength_[] = {14, 6, 22};
vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
int enemyStrength_[] = {8, 33};
vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
long long enemyCount_[] = {9, 1};
vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
long long _ = -1LL;
END
CASE(3)
int magicalGirlStrength_[] = {869, 249, 599, 144, 929, 748, 665, 37, 313, 99, 33, 437, 308, 137, 665, 834, 955, 958, 613, 417};
vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
int enemyStrength_[] = {789, 57, 684, 741, 128, 794, 542, 367, 937, 739, 568, 872, 127, 261, 103, 763, 864, 360, 618, 307};
vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
long long enemyCount_[] = {20626770196420, 45538527263992, 52807114957507, 17931716090785, 65032910980630, 88711853198687, 26353250637092,
61272534748707, 89294362230771, 52058590967576, 60568594469453, 23772707032338, 43019142889727, 39566072849912,
78870845257173, 68135668032761, 36844201017584, 10133804676521, 6275847412927, 37492167783296};
vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
long long _ = 75030497287405LL;
END
CASE(4)
int magicalGirlStrength_[] = {66,16,15,85,98,82,100,21,87,21,63,48,22,82,49,91,69,85,82,100,70,40,77,53,36,8,54,26,35,7,36,74,36,70,10,30,89,14,14,64,89,87,68,40,16,46,28,75,43,10};
vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
int enemyStrength_[] = {1};
vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
long long enemyCount_[] = {100000000000LL};
vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
long long _ = -1LL;
END
/*
CASE(5)
int magicalGirlStrength_[] = ;
vector <int> magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_));
int enemyStrength_[] = ;
vector <int> enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_));
long long enemyCount_[] = ;
vector<long long> enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_));
long long _ = LL;
END
*/
}
// END CUT HERE