#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef long long int ll; #define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout< ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } template T& maxset(T& to, const T& val) { return to = max(to, val); } template T& minset(T& to, const T& val) { return to = min(to, val); } void bye(string s, int code = 0) { cout << s << endl; exit(0); } mt19937_64 randdev(8901016); inline ll rand_range(ll l, ll h) { return uniform_int_distribution(l, h)(randdev); } #if defined(_WIN32) || defined(_WIN64) #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #elif __GNUC__ #else #define getchar_unlocked getchar #define putchar_unlocked putchar #endif namespace { #define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E) class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(string& var) { int cc = getchar_unlocked(); for (; !isvisiblechar(cc); cc = getchar_unlocked()); for (; isvisiblechar(cc); cc = getchar_unlocked()) var.push_back(cc); } template void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; } }; class MaiPrinter { public: template void output_integer(T var) { if (var == 0) { putchar_unlocked('0'); return; } if (var < 0) putchar_unlocked('-'), var = -var; char stack[32]; int stack_p = 0; while (var) stack[stack_p++] = '0' + (var % 10), var /= 10; while (stack_p) putchar_unlocked(stack[--stack_p]); } inline MaiPrinter& operator<<(char c) { putchar_unlocked(c); return *this; } inline MaiPrinter& operator<<(int var) { output_integer(var); return *this; } inline MaiPrinter& operator<<(long long var) { output_integer(var); return *this; } inline MaiPrinter& operator<<(char* str_p) { while (*str_p) putchar_unlocked(*(str_p++)); return *this; } inline MaiPrinter& operator<<(const string& str) { const char* p = str.c_str(); const char* l = p + str.size(); while (p < l) putchar_unlocked(*p++); return *this; } template void join(IT begin, IT end, char sep = '\n') { for (auto it = begin; it != end; ++it) *this << *it << sep; } }; } MaiScanner scanner; MaiPrinter printer; // ================================================================= // ================================================================= struct bamboo { bamboo(int l = 0, int w = 0) {} int length; int price; }; ostream& operator <<(ostream &o, const bamboo p) { o << make_pair(p.length, p.price); return o; } inline bool iskadomatsu(int a, int b, int c) { return a!=c && ((ac)||(a>b && b bb; // DP配列 // dp[重さ][直前の直前の竹の長さ][直前の竹の長さ] int dp[55][55][55]; int main() { // 読み込み scanner >> n >> capacity; if (n <= 2) bye("0"); bb.resize(n); repeat(i, n) { scanner >> bb[i].length; } repeat(i, n) { scanner >> bb[i].price; } int answer = 0; // 1番目に選ぶ竹 for (int i = 0; i < n; ++i) { // 2番目に選ぶ竹 for (int j = 0; j < n; ++j) { // 隣り合う竹の長さが同じ場合,門松列列の条件は満たさない. if (bb[i].length == bb[j].length) continue; // 予算が足りない if (bb[i].price + bb[j].price > capacity) continue; // maxset( dp[bb[i].price + bb[j].price][bb[i].length][bb[j].length], bb[i].length + bb[j].length ); } } // w円を既に消費した for (int w = 2; w < capacity; ++w) { // 番号iの竹を買おうとしている for (int i = 0; i < n; ++i) { // 予算が足りないなら遷移しない if (w + bb[i].price > capacity) continue; // もし直前の直前に選んだ竹の長さがl1,直前に選んだ竹の長さがl2ならば for (int l1 = 1; l1 <= 50; ++l1) { for (int l2 = 1; l2 <= 50; ++l2) { // 門松列列の条件を満たしていないので遷移しない if (!iskadomatsu(l1, l2, bb[i].length)) continue; // そのような状況は存在しないので遷移しない if (dp[w][l1][l2] == 0) continue; // maxset( dp[w + bb[i].price][l2][bb[i].length], dp[w][l1][l2] + bb[i].length ); maxset(answer, dp[w][l1][l2] + bb[i].length); } } } } printer << answer << '\n'; return 0; }