//#define NDEBUG #pragma GCC optimize("O3","unroll-loops","omit-frame-pointer","inline") //Optimization flags //#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX #pragma GCC target("avx") //Enable AVX #ifndef _MSC_VER #include //AVX/SSE Extensions #endif #ifdef _MSC_VER #pragma warning(1:4456) #endif #define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #define ALL(a) (a).begin(),(a).end() #define MEM2LOC(type,name) type name=(this->name); #define MEM2LOC_V(type,name) type name=((this->name).data()); #define LOC2MEM(name) (this->name)=(name); #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace chrono; namespace ValLib { constexpr double DIST_INF=1e100; constexpr int DX4[]={0,-1,0,1}; constexpr int DY4[]={-1,0,1,0}; constexpr int DX8[]={0,-1,-1,-1,0,1,1,1}; constexpr int DY8[]={-1,-1,0,1,1,1,0,-1}; constexpr int DX5[]={DX4[0],DX4[1],DX4[2],DX4[3],0}; constexpr int DY5[]={DY4[0],DY4[1],DY4[2],DY4[3],0}; constexpr int DX9[]={DX8[0],DX8[1],DX8[2],DX8[3],DX8[4],DX8[5],DX8[6],DX8[7],0}; constexpr int DY9[]={DY8[0],DY8[1],DY8[2],DY8[3],DY8[4],DY8[5],DY8[6],DY8[7],0}; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; constexpr ll V_MOD = 998244353ll; constexpr int V_INT_MAX = 2147483647; constexpr ll V_LL_MAX = 9223372036854775807ll; constexpr ull V_ULL_MAX = 18446744073709551615ull; templateusing array1=array; templateusing array2=array,A>; templateusing array3=array,B>,A>; templateusing array4=array,C>,B>,A>; templateusing array5=array,D>,C>,B>,A>; templateusing vector1=vector; templateusing vector2=vector>; templateusing vector3=vector>>; templateusing vector4=vector>>>; templateusing vector5=vector>>>>; templateclass tuple3{public:T a,b,c;tuple3()=default;tuple3(const T&a,const T&b,const T&c):a(a),b(b),c(c){}}; templateusing umap=std::unordered_map; templateusing uset=std::unordered_set; templateusing sptr=typename std::shared_ptr; templateusing iter_cat_type=typename std::iterator_traits<_Iter>::iterator_category; templateconstexpr bool _is_iterator=false; templateconstexpr bool _is_iterator<_Ty,std::void_t>> = true; templatevoid fill(vector&a,const T&v){std::fill(ALL(a),v);} templatevoid fill(vector>&a,const T&v){for(vector&t:a)std::fill(ALL(t),v);} templatevoid resize(vector&a,int sz1){a.resize(sz1);} templatevoid resize(vector&a,int sz1,const T&v){a.resize(sz1,v);} templatevoid resize(vector>&a,int sz1,int sz2){a.resize(sz1);for(vector&t:a)t.resize(sz2);} templatevoid resize(vector>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(vector&t:a)t.resize(sz2,v);} templatevoid assign(vector&a,int sz1,const T&v){a.assign(sz1,v);} templatevoid assign(vector>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(vector&t:a)t.assign(sz2,v);} templatevoid fill(array&a,const T&v){std::fill(ALL(a),v);} templatevoid fill(array2&a,const T&v){for(array&t:a)std::fill(ALL(t),v);} templateostream&operator<<(ostream&os,const pair&pr){os<<"{"<ostream&operator<<(ostream&os,vector&a){for(int i=0;iostream&operator<<(ostream&os,const array&a){os<<"[";for(int i=0;iostream&operator<<(ostream&os,const map&m){os<<"{";auto b=m.begin();auto e=m.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<first<<":"<second;}os<<"}";return os;} templateostream&operator<<(ostream&os,const set&s){os<<"{";auto b=s.begin();auto e=s.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<*p;}os<<"}";return os;} templateostream&operator<<(ostream&os,const unordered_map&m){os<<"{";auto b=m.begin();auto e=m.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<first<<":"<second;}os<<"}";return os;} templateostream&operator<<(ostream&os,const unordered_set&s){os<<"{";auto b=s.begin();auto e=s.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<*p;}os<<"}";return os;} constexpr ll mod_add(ll a,ll b,ll mod){return((a%mod)+(b%mod))%mod;} constexpr ll mod_sub(ll a,ll b,ll mod){return((a%mod)+mod-(b%mod))%mod;} // a>bだとmod-(b-a)が返る constexpr ll mod_mul(ll a,ll b,ll mod){return((a%mod)*(b%mod))%mod;} constexpr ull mod_add(ull a,ull b,ull mod){return((a%mod)+(b%mod))%mod;} constexpr ull mod_sub(ull a,ull b,ull mod){return((a%mod)+mod-(b%mod))%mod;} // a>bだとmod-(b-a)が返る constexpr ull mod_mul(ull a,ull b,ull mod){return((a%mod)*(b%mod))%mod;} constexpr int intPow(int x,int n){assert(x>=0);assert(n>=0);if(x==0){if(n==0){return 1;}else{return 0;}}int r=1,z=x;while(n>0){if(n&1){r*=z;}z*=z;n>>=1;}return r;} constexpr ll intPow(ll x,ll n){assert(x>=0ll);assert(n>=0ll);if(x==0ll){if(n==0ll){return 1ll;}else{return 0ll;}}ll r=1ll,z=x;while(n>0ll){if(n&1ll){r*=z;}z*=z;n>>=1ll;}return r;} constexpr ll intPow(ll x,ll n,ll mod){assert(x>=0ll);assert(n>=0ll);if(x==0ll){if(n==0ll){return 1ll;}else{return 0ll;}}ll r=1ll,z=x;while(n>0ll){if(n&1ll){if(mod>0ll){r=mod_mul(r,z,mod);}else{r*=z;}}if(mod>0ll){z=mod_mul(z,z,mod);}else{z*=z;}n>>=1ll;}return r;} constexpr ull intPow(ull x,ull n){if(x==0ull){if(n==0ull){return 1ull;}else{return 0ull;}}ull r=1ull,z=x;while(n>0ull){if(n&1ull){r*=z;}z*=z;n>>=1ull;}return r;} constexpr ull intPow(ull x,ull n,ull mod){if(x==0ull){if(n==0ull){return 1ull;}else{return 0ull;}}ull r=1ull,z=x;while(n>0ull){if(n&1ull){if(mod>0ull){r=mod_mul(r,z,mod);}else{r*=z;}}if(mod>0ull){z=mod_mul(z,z,mod);}else{z*=z;}n>>=1ull;}return r;} constexpr ll mod_inv(ll a,ll mod){return intPow(a%mod,mod-2ll,mod);} constexpr ll mod_div(ll a,ll b,ll mod){return mod_mul(a,mod_inv(b,mod),mod);} constexpr ull mod_inv(ull a,ull mod){return intPow(a%mod,mod-2ull,mod);} constexpr ull mod_div(ull a,ull b,ull mod){return mod_mul(a,mod_inv(b,mod),mod);} typedef pair pii; typedef pair pll; typedef pair pdd; ll ceilDiv(ll a,ll b){return a/b+(a%b!=0?1:0);} ll isOverflowAdd(ll a,ll b){return a > V_LL_MAX - b;} ll isOverflowMul(ll a,ll b){return a > V_LL_MAX / b;} void debugErrSub(); templatevoid debugErrSub(Head&&head,Tail&&...tail){cerr<<" "<(tail)...);} templatevoid debugErr(Head&&head,Tail&&...tail){cerr<(tail)...);} template bool containsKey(const umap& m, const Key& key) { return m.find(key) != m.end(); } template bool containsValue(const umap& m, const Value& val) { for (auto it = m.begin(); it != m.end(); ++it) if (it->second == val) return true; return false; } template const typename uset::const_iterator find(const uset& s, const T& key) { return s.find(key); } template bool contains(const uset& s, const T& key) { return s.find(key) != s.end(); } #ifndef __GNUC__ int __builtin_popcount(unsigned int n){return(int)bitset<32>(n).count();} int __builtin_popcountll(unsigned long long n){return(int)bitset<64>(n).count();} #endif // 条件を満たす最小の要素のindexを返す // lb: lower bound. 条件式を満たさない // ub: upper bound. 条件式を満たす // check: 条件式 // 使い方の例: int result = binarySearch(A, 0, N - 1, [&](int x) { return x >= K; }); template int binarySearch(const vector& vec, int beginIndex, int endIndex, const function& confilm) { int lb = beginIndex; // lower bound int ub = endIndex; // upper bound while (abs(ub - lb) > 1) { int mid = (ub + lb) / 2; if (confilm(vec[mid])) { ub = mid; } else { lb = mid; } } return ub; } // lb: lower bound. 条件式を満たさない // ub: upper bound. 条件式を満たす // check: 条件式 ll binarySearch(ll lb, ll ub, const function& check) { while (abs(ub - lb) > 1ll) { ll mid = (lb + ub) / 2ll; if (check(mid)) { ub = mid; } else { lb = mid; } } return ub; } // lb: lower bound. 条件式を満たさない // ub: upper bound. 条件式を満たす // check: 条件式 ull binarySearch(ull lb, ull ub, const function& check) { assert(ub > lb); while (ub - lb > 1ull) { ull mid = (lb + ub) / 2ull; if (check(mid)) { ub = mid; } else { lb = mid; } } return ub; } // lb: lower bound. 条件式を満たさない // ub: upper bound. 条件式を満たす // check: 条件式 long double binarySearch(long double lb, long double ub, const function& check) { while (fabs(ub - lb) > (long double)1e-15) { long double mid = (lb + ub) / 2.0L; if (check(mid)) { ub = mid; } else { lb = mid; } } return ub; } // 最大公約数(ユーグリッドの互除法) static constexpr ull gcd(ull x, ull y) { assert(x > 0ull); assert(y > 0ull); ull r = 0ull; while ((r = x % y) != 0ull) { x = y; y = r; } return y; } // 最小公倍数 static constexpr ull lcm(ull x, ull y) { assert(x > 0ull); assert(y > 0ull); return x / gcd(x, y) * y; } // 文字列の先頭の0を削除する string cutZeroLeft(const string& str) { for (int i = 0; i < (int)str.length(); ++i) { if (str[i] != '0') { return str.substr(i); } } return ""; } // 0以上の整数を0埋めで表記する string fillZero(ull number, int digit) { int zeroNum = max(0, (int)(digit - to_string(number).length())); return move(move(string(zeroNum, '0')) + move(to_string(number))); } // double型の値を任意の少数桁数で表示する // 指定の桁数まで0で埋める。指数表記にはならない // precision=0を指定したときは小数点は表示しない // 表示桁数+1桁目を四捨五入する string sprintDoublePlane(double value, int precision) { assert(precision >= 0); stringstream ss; ss << fixed << setprecision(precision) << value; return move(ss.str()); } templatevoid in(A&a){cin>>a;cin.ignore();} templatevoid in(A&a,B&b){cin>>a>>b;cin.ignore();} templatevoid in(A&a,B&b,C&c){cin>>a>>b>>c;cin.ignore();} templatevoid in(A&a,B&b,C&c,D&d){cin>>a>>b>>c>>d;cin.ignore();} templatevoid in(A&a,B&b,C&c,D&d,E&e){cin>>a>>b>>c>>d>>e;cin.ignore();} templatevoid in(A&a,B&b,C&c,D&d,E&e,F&f){cin>>a>>b>>c>>d>>e>>f;cin.ignore();} templatevoid in(A&a,B&b,C&c,D&d,E&e,F&f,G&g){cin>>a>>b>>c>>d>>e>>f>>g;cin.ignore();} templatevoid inr(vector&a,int size){resize(a,size);for(int i=0;i>a[i];cin.ignore();}} templatevoid inr(vector&a,vector&b,int size){resize(a,size);resize(b,size);for(int i=0;i>a[i]>>b[i];cin.ignore();}} templatevoid inr(vector&a,vector&b,vector&c,int size){resize(a,size);resize(b,size);resize(c,size);for(int i=0;i>a[i]>>b[i]>>c[i];cin.ignore();}} templatevoid inr(vector&a,vector&b,vector&c,vector&d,int size){resize(a,size);resize(b,size);resize(c,size);resize(d,size);for(int i=0;i>a[i]>>b[i]>>c[i]>>d[i];cin.ignore();}} templatevoid inr(vector&a,vector&b,vector&c,vector&d,vector&e,int size){resize(a,size);resize(b,size);resize(c,size);resize(d,size);resize(e,size);for(int i=0;i>a[i]>>b[i]>>c[i]>>d[i]>>e[i];cin.ignore();}} templatevoid inrl(vector&a,int size){resize(a,size);for(int i=0;i>a[i];}cin.ignore();} templatevoid inr(vector2&a,int h,int wa){resize(a,h,wa);for(int i=0;i>a[i][j];}cin.ignore();}} templatevoid inr(vector2&a,vector2&b,int h,int wa,int wb){resize(a,h,wa);resize(b,h,wb);for(int i=0;i>a[i][j];}for(int j=0;j>b[i][j];}cin.ignore();}} templatevoid inr(vector2&a,vector2&b,vector2&c,int h,int wa,int wb,int wc){resize(a,h,wa);resize(b,h,wb);resize(c,h,wc);for(int i=0;i>a[i][j];}for(int j=0;j>b[i][j];}for(int j=0;j>c[i][j];}cin.ignore();}} templatevoid inpr(vector>&a,int h){resize(a,h);for(int i=0;i>a[i].first>>a[i].second;cin.ignore();}} templatevoid out(const T&val){cout<>19))^(t^(t>>8));} void solve() { ll N, M, W; in(N, M, W); vector A, B, C, D; inrl(A, (int)N); inrl(B, (int)N); inrl(C, (int)M); inrl(D, (int)M); vector2 w(1 << N, vector(1 << M, 0)); for (int a = 0; a < (1 << N); ++a) { for (int b = 0; b < (1 << M); ++b) { ll weight = 0; for (int i = 0; i < N; ++i) { if (a & (1 << i)) { weight += A[i]; } } for (int j = 0; j < M; ++j) { if (b & (1 << j)) { weight -= C[j]; } } w[a][b] = weight; } } vector2 dp(1 << N, vector(1 << M, -V_LL_MAX)); dp[0][0] = 0; for (int a = 0; a < (1 << N); ++a) { for (int b = 0; b < (1 << M); ++b) { if (w[a][b] < 0 || w[a][b] > W || dp[a][b] == -V_LL_MAX) { continue; } for (int j = 0; j < M; ++j) { if (!(b & (1 << j)) && w[a][b] - C[j] >= 0) { dp[a][b | (1 << j)] = max(dp[a][b | (1 << j)], dp[a][b] - D[j]); } } } for (int b = 0; b < (1 << M); ++b) { if (w[a][b] < 0 || w[a][b] > W || dp[a][b] == -V_LL_MAX) { continue; } for (int i = 0; i < N; ++i) { if (!(a & (1 << i)) && w[a][b] + A[i] <= W) { dp[a | (1 << i)][b] = max(dp[a | (1 << i)][b], dp[a][b] + B[i]); } } } } ll ans = 0; for (int a = 0; a < (1 << N); ++a) { for (int b = 0; b < (1 << M); ++b) { ans = max(ans, dp[a][b]); } } out(ans); } int main() { std::ios::sync_with_stdio(false); //#define INPUT_FROM_FILE //#define OUTPUT_TO_FILE #ifdef INPUT_FROM_FILE ifstream ifs("input01.txt"); cin.rdbuf(ifs.rdbuf()); #endif #ifdef OUTPUT_TO_FILE ofstream ofs("output01.txt"); cout.rdbuf(ofs.rdbuf()); #endif solve(); }