#pragma GCC target ("avx2")
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef unsigned int uint;
typedef unsigned long long ull;
//typedef tree<int, null_type, std::less<>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//typedef tree<pair<int, int>, null_type, greater<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define er "\n"
#define rep(i, x, y) for(int i = x; i < y; ++i)
#define Rep(i, x, y) for(int i = x; i <= y; ++i)
#define sRep(i, x, y) for(int i = x; i >= y; --i)
#define ite(it,s) for(auto it = s.begin(); it!=s.end(); ++it)
#define getBit(x,i) (x&(1<<i))
#define setBit(x,i) (x|(1<<i))
#define mid(L,R) ((L+R)/2)
#define mem(A,N) memset(A,N,sizeof(A))
#define sz(x) ((int)(x).size())
#define all(v) v.begin(),v.end()
#define rev(v) reverse(v.begin(),v.end())
#define Sort(x) sort(x.begin(),x.end());
// vector/deque
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
// pairs
#define mp make_pair
#define fi first
#define se second
// Less common loops
#define srep(i, x, y) for(int i = x; i > y; --i)
#define rep2(i, x, y) for(int i = x; i < y; i+=2)
#define Rep2(i, x, y) for(int i = x; i <= y; i+=2)
#define sRep2(i, x, y) for(int i = x; i >= y; i-=2)
#define srep2(i, x, y) for(int i = x; i > y; i-=2)
#define sumsTo(s) ((int)((-1+sqrt(1+8*s))/2))
#define inBounds(x,y) (x >= 0 && x < n && y >= 0 && y < m)
#define isInt(x) ((int) floor(x)==x)
#define yes() (cout << "yes\n");
#define no() (cout << "no\n");
#define Yes() (cout << "YES\n");
#define No() (cout << "NO\n");
#define yes2() (cout << "Yes\n");
#define no2() (cout << "No\n");
#define linf 1000000000000000001LL
#define inf 1000000001
#define mod 1000000007
#define eps 1e-9
#define Pi 3.14159265358979323846
// Debug
#ifndef ONLINE_JUDGE
#define dump(x) cerr << #x << "=" << (x) << endl;
#define write(x) cerr << #x << "=" << (x) << ", ";
#define writeSet(s) cerr << #s << "= "; for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cerr << *it : cerr << ' ' << *it;
#define dumpSet(s) cerr << #s << "= "; for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cerr << *it : cerr << ' ' << *it; cerr << endl;
#define writeMap(s) cerr << #s << "= "; for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cerr << it->first << ',' << it->second : cerr << ' ' << it->first << ',' << it->second;
#define dumpMap(s) cerr << #s << "= "; for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cerr << it->first << ',' << it->second : cerr << ' ' << it->first << ',' << it->second; cerr << endl;
// Debug - Printing loop counters (i,j,k,p)
#define writei cerr << "i = " << i << ".. ";
#define dumpi cerr << "i = " << i << endl;
#define writej cerr << "j = " << j << ".. ";
#define dumpj cerr << "j = " << j << endl;
#define writek cerr << "k = " << k << ".. ";
#define dumpk cerr << "k = " << k << endl;
#define writep cerr << "p = " << p << ".. ";
#define dumpp cerr << "p = " << p << endl;
#endif
//void __print(int x) {cerr << x;} string __strprint(int x) {return to_string(x);}
//void __print(long x) {cerr << x;} string __strprint(long x) {return to_string(x);}
//void __print(long long x) {cerr << x;} string __strprint(long long x) {return to_string(x);}
//void __print(unsigned x) {cerr << x;} string __strprint(unsigned x) {return to_string(x);}
//void __print(unsigned long x) {cerr << x;} string __strprint(unsigned long x) {return to_string(x);}
//void __print(unsigned long long x) {cerr << x;} string __strprint(unsigned long long x) {return to_string(x);}
//void __print(float x) {cerr << x;} string __strprint(float x) {return to_string(x);}
//void __print(double x) {cerr << x;} string __strprint(double x) {return to_string(x);}
//void __print(long double x) {cerr << x;} string __strprint(long double x) {return to_string(x);}
//void __print(char x) {cerr << '\'' << x << '\'';} string ___strprint(char x) {return "\'" + string(1,x) + "\'";}
//void __print(const char *x) {cerr << '\"' << x << '\"';} string __strprint(const char *x) {return "\"" + string(x) + "\"";}
//void __print(const string &x) {cerr << '\"' << x << '\"';} string __strprint(const string &x) {return "\"" + x + "\"";}
//void __print(bool x) {cerr << (x ? "true" : "false");} string ___strprint(bool x) {return (x ? "true" : "false");}
//
//template<typename T, typename V>
//void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
//template<typename T>
//void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
//void _print() {cerr << "]\n";}
//template <typename T, typename... V>
//void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
//
//template<typename T, typename V>
//string __strprint(const pair<T, V> &x) {string build="{"; build+=__strprint(x.first); build+=","; build+=__strprint(x.second); return build+"}";}
//template<typename T>
//string __strprint(const T &x) {int f = 0; string build="{"; for (auto &i: x) build+=(f++ ? "," : ""), build+=__strprint(i); return build+"}";}
//string _strprint() {return "]";}
//template <typename T, typename... V>
//string _strprint (T t, V... v) {string build=__strprint(t); if (sizeof...(v)) build+=", "; return build+_strprint(v...);}
//string _strdebug(x...) (stringstream ss; ss<<"["<<#x<<"] = ["<<_strprint(x); return ss.str();)
//ostream& operator << (ostream& os, const ii& p) { return (os << '(' << p.first << ',' << p.second << ')'); }
template<typename T, typename V> pair<T, V> operator + (const pair<T, V>& p1, const pair<T, V>& p2) { return make_pair(p1.first+p2.first,p1.second+p2.second); }
//template<typename T> typename T::iterator min_map_element(T& m) { return min_element(m.begin(), m.end(), [](typename T::value_type& l, typename T::value_type& r) -> bool { return l.second < r.second; }); }
//template<typename T> typename T::iterator max_map_element(T& m) { return max_element(m.begin(), m.end(), [](typename T::value_type& l, typename T::value_type& r) -> bool { return l.second < r.second; }); }
// Print
#define printArray(a,x,y) for(auto it = (a)+(x); it != (a)+(y); it++) (it==(a)+(x)) ? cout << *it : cout << ' ' << *it; cout << '\n';
#define PrintArray(a,x,y) for(auto it = (a)+(x); it != (a)+(y)+1; it++) (it==(a)+(x)) ? cout << *it : cout << ' ' << *it; cout << '\n';
#define sPrintArray(a,x,y) for(auto it = (a)+(x); it != (a)+(y)-1; it--) (it==(a)+(x)) ? cout << *it : cout << ' ' << *it; cout << '\n';
#define printVector(x) for(auto it = (x).begin(); it!=(x).end(); it++) (it==(x).begin()) ? cout << *it : cout << ' ' << *it; cout << '\n';
#define sprintVector(x) for(auto it = (x).rbegin(); it!=(x).rend(); it++) (it==(x).rbegin())? cout << *it : cout << ' ' << *it; cout << '\n';
#define sPrintVector(x) for(auto it = (x).rbegin(); it!=(x).rend(); it++) (it==(x).rbegin())? cout << *it : cout << ' ' << *it; cout << '\n'; // same as above one.
#define printSet(s) for(auto it = s.begin(); it!=s.end(); it++) (it==(s).begin()) ? cout << *it : cout << ' ' << *it; cout << '\n';
#define sprintSet(s) for(auto it = s.rbegin(); it!=s.rend(); it++) (it==(s).rbegin())? cout << *it : cout << ' ' << *it; cout << '\n';
#define printPairset(s) for(auto it = (s).begin(); it!=(s).end(); it++) (it==(s).begin()) ? cout << '(' << it->first << ',' << it->second << ')' : cout << " {" << it->first << ',' << it->second << '}'; cout << '\n';
#define sprintPairset(s) for(auto it = (s).rbegin(); it!=(s).rend(); it++) (it==(s).rbegin())? cout << '(' << it->first << ',' << it->second << ')' : cout << " {" << it->first << ',' << it->second << '}'; cout << '\n';
#define printArrayln(a,x,y) for(auto it = (a)+(x); it != (a)+(y); it++) (it==(a)+(x)) ? cout << *it : cout << '\n' << *it; cout << '\n';
#define PrintArrayln(a,x,y) for(auto it = (a)+(x); it != (a)+(y)+1; it++) (it==(a)+(x)) ? cout << *it : cout << '\n' << *it; cout << '\n';
#define sPrintArrayln(a,x,y) for(auto it = (a)+(x); it != (a)+(y)-1; it++) (it==(a)+(x)) ? cout << *it : cout << '\n' << *it; cout << '\n';
#define printVectorln(x) for(auto it = (x).begin(); it!=(x).end(); it++) (it==(x).begin()) ? cout << *it : cout << '\n' << *it; cout << '\n';
#define sprintVectorln(x) for(auto it = (x).rbegin(); it!=(x).rend(); it++) (it==(x).rbegin())? cout << *it : cout << '\n' << *it; cout << '\n';
#define sPrintVectorln(x) for(auto it = (x).rbegin(); it!=(x).rend(); it++) (it==(x).rbegin())? cout << *it : cout << '\n' << *it; cout << '\n'; // same as above one.
#define printSetln(s) for(auto it = s.begin(); it!=s.end(); it++) (it==(s).begin()) ? cout << *it : cout << '\n' << *it; cout << '\n';
#define sprintSetln(s) for(auto it = s.rbegin(); it!=s.rend(); it++) (it==(s).rbegin())? cout << *it : cout << '\n' << *it; cout << '\n';
#define printPairsetln(s) for(auto it = (s).begin(); it!=(s).end(); it++) (it==(s).begin()) ? cout << '(' << it->first << ',' << it->second << ')' : cout << "\n{" << it->first << ',' << it->second << '}'; cout << '\n';
#define sprintPairsetln(s) for(auto it = (s).rbegin(); it!=(s).rend(); it++) (it==(s).rbegin())? cout << '(' << it->first << ',' << it->second << ')' : cout << "\n{" << it->first << ',' << it->second << '}'; cout << '\n';
// Less common prints
#define sprintArray(a,x,y) for(auto it = (a)+(x); it != (a)+(y); it--) (it==(a)+(x)) ? cout << *it : cout << ' ' << *it; cout << '\n';
#define sprintArrayln(a,x,y) for(auto it = (a)+(x); it != (a)+(y); it--) (it==(a)+(x)) ? cout << *it : cout << '\n' << *it; cout << '\n';
ostringstream debug_sstr; string debug_str; vector<string> debug_strvec;
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#define sdebug(x...) (debug_sstr<<"["<<#x<<"]=["<<_strprint(x),debug_str=debug_sstr.str(),debug_sstr=ostringstream(),debug_str)
#define sDebugVector(v,a,x,y) for(auto it = (a)+(x); it != (a)+(y)+1; it++) (it==(a)+(x)) ? debug_sstr << *it : debug_sstr << ' ' << *it; (debug_str=debug_sstr.str(),debug_sstr=ostringstream(),(v).push_back(debug_str))
#define sDebugVector2(v,a,x,y) debug_strvec = vector<string>(); for(auto it = (a)+(x); it != (a)+(y)+1; it++) debug_strvec.push_back(to_string(*it)); v.push_back(debug_strvec);
#else
#define debug(x...)
#endif
#ifndef OUTPUT_PATH
#define fout(x) fout;(&fout)->basic_ios<char>::rdbuf(cout.rdbuf());
#endif
// ***************** End Of Template ********************
int n, w;
int a[20000];
//tuple<int,int,int> ks[2][75001];
ii ks[75001];
ii ks2[75001];
ii ans;
vector<bool>* knapsack_(int startItem, int N, int startWeight, int W, int* a, int* ar) {
if (startItem == N) return new vector<bool> ();
if (N - startItem == 1) if (a[startItem] <= (W-startWeight)) return new vector<bool> {1}; else return new vector<bool> {0};
memset(ks + startWeight, 0, (W - startWeight + 1)*8);
memset(ks2 + startWeight, 0, (W - startWeight + 1)*8);
// Rep(i,startWeight,W) ks[i] = ks2[i] = mp(0,0);
int mid = (startItem + N + 1) / 2;
for (int i = startItem; i < mid; i++) {
int weight = a[i];
for (int j = W; j >= startWeight+weight; j--)
ks[j] = max(ks[j], mp(ks[j-weight].fi+weight,ks[j-weight].se-1));
}
for (int i = N-1; i >= mid; i--) {
int weight = a[i];
for (int j = startWeight; j <= W-weight; j++)
ks2[j] = max(ks2[j], mp(ks2[j+weight].fi+weight,ks2[j+weight].se-1));
}
ii bestSplitLength = mp(-inf,-inf); int bestSplitIdx = startWeight;
for (int j = startWeight; j <= W; j++) {
ii curSplit = ks[j] + ks2[j];
if (curSplit > bestSplitLength) {
bestSplitLength = curSplit; bestSplitIdx = j;
}
else if (curSplit == bestSplitLength && (abs(mid-j) < abs(mid-bestSplitIdx))) {
bestSplitLength = curSplit; bestSplitIdx = j;
}
}
if (N == n) ans = bestSplitLength;
vector<bool>* v1 = knapsack_(startItem, mid, startWeight, bestSplitIdx, a, ar);
vector<bool>* v2 = knapsack_(n - N, n - mid, w - W, w - bestSplitIdx, ar, a);
v1->insert(v1->end(),v2->rbegin(),v2->rend());
return v1;
}
vector<bool>* knapsack(int startItem, int N, int startWeight, int W, int* a) {
int ar[N]; for(int i = 0; i != N; i++) ar[i] = a[N-1-i];
return knapsack_(startItem, N, startWeight, W, a, ar);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("ghiozdan.in", "r", stdin);
freopen("ghiozdan.out", "w", stdout);
cin >> n >> w;
rep(i,0,n) {
cin >> a[i];
}
vector<bool>* x = knapsack(0,n,0,w,a);
cout << ans.fi << ' ' << -ans.se;
for (int i = 0; i != x->size(); i++) if ((*x)[i]) cout << '\n' << a[i];
// sort(a,a+n);
// set<int> s;
// rep(i,0,n) s.insert(a[i]);
// Rep(i,0,w) ks[0][i] = make_tuple(0,0,0);
// int cur = 0, prv = 1;
// int last = 0;
// rep(i,0,n) {
// int weight = a[i];
// if (weight != last) { v.push_back(get<0>(ks[cur][w])); last = weight; }
// swap(cur,prv);
// Rep(j,weight,w) {
// tuple<int,int,int> y = ks[prv][j-weight];
// ks[cur][j] = max(ks[prv][j], make_tuple(get<0>(y)+weight, get<1>(y)-1, -weight));
// }
// }
// v.push_back(get<0>(ks[cur][w]));
// cout << get<0>(ks[cur][w]) << ' ' << -get<1>(ks[cur][w]) << endl;
// printVector(v);
// int i = v.size()-1;
// auto it = --s.end();
// int weightReached = get<0>(ks[cur][w]);
// vi ans_v;
// while (true) {
// int weight = *it;
// if (weightReached == v[i]) { i--; it--; if (i < 0) break; }
// else {
// weightReached -= weight;
// ans_v.push_back(weight);
// }
// }
// rev(ans_v);
// printVector(ans_v);
return 0;
}
Karim Elsheikh KarimElSheikh