#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>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class KiwiJuice { public:
int theProfit(int C, vector <int> bottles, vector <int> prices)
{
best.clear();
best.resize(1<<bottles.size(), -1);
return rec((1<<bottles.size())-1, C, bottles, prices);
}
vector<int> best;
int rec(int mask, int C, vector<int>& B, const vector<int>& P)
{
if( mask == 0 )
return 0;
if( best[mask] != -1 )
return best[mask];
int maxSc = 0;
for(int subset=mask; subset; subset=((subset-1)&mask)) {
int sum = 0;
int bin = 0;
for(int i=0; i<B.size(); ++i)
if( subset & (1<<i) ) {
sum += B[i];
bin += 1;
}
int sc = P[C] * (sum/C);
if(sum%C) sc += P[sum%C];
sc += P[0] * (bin-((sum/C)+(sum%C?1:0)));
sc += rec(mask&~subset, C, B, P);
maxSc = max(maxSc, sc);
}
return best[mask] = maxSc;
}
};
// 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 int& Expected, const int& 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(_, KiwiJuice().theProfit(C, bottles, prices));}
int main(){
CASE(0)
int C = 10;
int bottles_[] = {5, 8};
vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
int prices_[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10};
vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
int _ = 10;
END
CASE(1)
int C = 10;
int bottles_[] = {5, 8};
vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
int prices_[] = {0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10};
vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
int _ = 20;
END
CASE(2)
int C = 10;
int bottles_[] = {4, 5, 3, 7};
vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
int prices_[] = {14, 76, 12, 35, 6, 94, 26, 3, 93, 90, 420};
vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
int _ = 625;
END
CASE(3)
int C = 1;
int bottles_[] = {0};
vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
int prices_[] = {1000000, 1000000};
vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
int _ = 1000000;
END
CASE(4)
int C = 49;
int bottles_[] = {2, 47, 24, 14, 0, 32, 9, 12, 31, 46, 39, 12, 16, 22, 29};
vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
int prices_[] = {428668, 995687, 128567, 37241, 496916, 238624, 304781, 997819, 85856, 417008,
398570, 951499, 750349, 333625, 927594, 188616, 942498, 259414, 654344, 354809,
25303, 226854, 98578, 207140, 305527, 358343, 393213, 256248, 282644, 103327,
667191, 103402, 609183, 619323, 189127, 518006, 778846, 400460, 128334, 795097,
605203, 669142, 121825, 934404, 837430, 554265, 610818, 546228, 80784, 949440};
vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
int _ = 12873962;
END
CASE(5)
int C = 10;
int bottles_[] = {2,3,5};
vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
int prices_[] = {0,0,9,9,0,9,0,0,0,0,99};
vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
int _ = 99;
END
/*
CASE(6)
int C = ;
int bottles_[] = ;
vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_));
int prices_[] = ;
vector <int> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices_));
int _ = ;
END
*/
}
// END CUT HERE