1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse4")

#include <bits/stdc++.h>

using namespace std;

#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME
#define __FOR3(i, a, n, inc) for(int i = (a); (inc) > 0 ? i < (n) : i >= (n); i += (inc))
#define __FOR2(i, a, n) __FOR3(i, a, n, 1)
#define __FOR1(i, n) __FOR2(i, 0, n)
#define FOR(...) GET_MACRO(__VA_ARGS__, __FOR3, __FOR2, __FOR1)(__VA_ARGS__)

#define BOOST 			ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ELO             exit(0)
#define ALL(a) 			(a).begin(), (a).end()
#define SZ(a) 			(int)(a).size()
#define TRAV(a, b) 		for (auto& a : b)
#define REV(a)          reverse(ALL(a))
#define SORT(a)         sort(ALL(a))
#define SORTR(a)        SORT(a), REV(a)
#define PB              push_back
#define F               first
#define S               second
using ll = 				long long;
using ld = 				long double; // 'long double' is 2.2 times slower than double
using pii = 			pair<int, int>;
using pll = 			pair<ll, ll>;
using pld =             pair<ld, ld>;
using vi = 				vector<int>;
using vvi =             vector<vi>;
using vll = 			vector<ll>;
using vvll =            vector<vll>;
using vpii = 			vector<pii>;
using vpll = 			vector<pll>;
using vld =             vector<ld>;
using vpld =            vector<pld>;

constexpr int MOD = 1e9 + 7; // 998244353
constexpr int INF = MOD;
constexpr ll LLINF = 1e18;
const ld PI = acos(-1);

template <class T> inline bool setmin(T& a, T b) {if (a > b) return a = b, 1; return 0; }
template <class T> inline bool setmax(T& a, T b) {if (a < b) return a = b, 1; return 0; }

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class key, class cmp = less<key>> using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template <class key, class cmp = less_equal<key>> using ordered_multiset = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
//* find_by_order(k) - returns an iterator to the k-th largest element (counting from zero)
//* order_of_key(k)  - the number of items in a set that are strictly smaller than k.
template <class key, class value, class cmp = less<key>> using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
using pref_trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;
// * prefix_range(s) - return iterator range, prefix equal to s

namespace input {
    template <class T> istream &operator>>(istream &os, vector<T> & vec) { for (auto& u : vec) os >> u; return os; }
    template<class T1, class T2> istream& operator>>(istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
    template <class T, size_t N> istream& operator>>(istream& os, array<T, N>& a) { for (auto& u : a) os >> u; return os; }

    void re() {}
    template <typename T, typename... args> void re(T& x, args&... tail) { cin >> x; re(tail...); }
} // namespace input
using namespace input;

namespace output {
    template <class T> ostream &operator<<(ostream &os, const vector<T> & vec){for (const auto& u : vec) os << u << " "; return os; }
    template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << p.first << " " << p.second; }
    template <class T> ostream &operator<<(ostream &os, set<T> & con) { for (const auto& u : con) os << u << " "; return os; }
    template <class T, size_t N> ostream& operator<<(ostream& os, array<T, N>& a) { for (const auto& u : a) os << u << " "; return os; }
    
    void pr() {}
    template <typename T> void pr(const T& x) { cout << x; }
    template <typename T, typename... args> void pr(const T& x, const args&... tail) { cout << x << " "; pr(tail...);}
    template <typename T> void prs(const T& x) { cout << x << " "; }
    template <typename T, typename... args> void prs(const T& x, const args&... tail) { cout << x << " "; prs(tail...);}
    template <typename... args> void prln(const args&... tail) { pr(tail...); cout << "\n";}
} // namespace output 
using namespace output;

namespace pair_magic {
	#define PT1T2 pair<T1,T2>
	#define TT1T2 template<class T1, class T2>
	TT1T2 inline PT1T2 operator+(const PT1T2 &p1, const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
	TT1T2 inline PT1T2& operator+=(PT1T2 &p1, const PT1T2 &p2) { p1.first += p2.first, p1.second += p2.second; return p1; }
	TT1T2 inline PT1T2 operator-(const PT1T2 &p1, const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
	TT1T2 inline PT1T2& operator-=(PT1T2 &p1, const PT1T2 &p2) { p1.first -= p2.first, p1.second -= p2.second; return p1; }
	#undef PT1T2
	#undef TT1T2
}
using namespace pair_magic;

namespace random_nsp {
	thread_local std::mt19937 gen{std::random_device{}()};
	template <typename T>T random(T min, T max){using dist = std::conditional_t<std::is_integral<T>::value, std::uniform_int_distribution<T>, std::uniform_real_distribution<T>>;return dist{min, max}(gen);}
	template <typename T> T randomINT(T min, T max) { return std::uniform_int_distribution<T>{min, max}(gen); }
}
using namespace random_nsp;

namespace triple {
	#define TT1T2T3 template<class T1, class T2, class T3>
	#define TRT1T2T3  triple<T1, T2, T3>
	TT1T2T3 struct triple { T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c) {} };
	TT1T2T3 bool operator<(const TRT1T2T3&t1, const TRT1T2T3&t2) { if (t1.a != t2.a)return t1.a < t2.a; else if (t1.b != t2.b)return t1.b < t2.b; else return t1.c < t2.c; }
	TT1T2T3 bool operator>(const TRT1T2T3&t1, const TRT1T2T3&t2) { if (t1.a != t2.a)return t1.a > t2.a; else if (t1.b != t2.b)return t1.b > t2.b; else return t1.c > t2.c; }
	TT1T2T3 bool operator==(const TRT1T2T3&t1, const TRT1T2T3&t2) { return (t1.a == t2.a && t1.b == t2.b && t1.c == t2.c); }
	TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
	TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t) { return os << t.a << " " << t.b << " " << t.c; }
	#undef TRT1T2T3
	#undef TT1T2T3
	using tri =  triple<int, int, int>;
	using trll = triple<ll, ll, ll>;
	using vtri = vector<tri>;
    using vtrll = vector<trll>;
}
using namespace triple;

template <class T> T invGeneral(T a, T b) { // 0 < a < b, gcd(a,b) = 1
    a %= b;
    if (a == 0) return b == 1 ? 0 : -1;
    T x = invGeneral(b, a); 
    return x == -1 ? -1 : ((1-(ll)b * x) / a + b) % b;
}

template<class T, int MOD> struct modular {
	T val; 
	explicit operator T() const { return val; }
	modular() { val = 0; }
	modular(const ll& v) { 
		val = (-MOD <= v && v <= MOD) ? v : v % MOD;
		if (val < 0) val += MOD;
	}
	
	friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; }
	friend void pr(const modular& a) { pr(a.val); }
	friend void re(modular& a) { ll x; re(x); a = modular(x); }
   
	friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; }
	friend bool operator!=(const modular& a, const modular& b) { return !(a == b); }
	friend bool operator<(const modular& a, const modular& b) { return a.val < b.val; }
 
	modular operator-() const { return modular(-val); }
	modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	modular& operator*=(const modular& m) { val = (ll)val*m.val%MOD; return *this; }
	friend modular pow(modular a, ll p) {
		modular ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend modular inv(const modular& a) { 
		auto i = invGeneral(a.val,MOD); assert(i != -1);
		return i;
	} // equivalent to return exp(b,MOD-2) if MOD is prime
	modular& operator/=(const modular& m) { return (*this) *= inv(m); }
	
	friend modular operator+(modular a, const modular& b) { return a += b; }
	friend modular operator-(modular a, const modular& b) { return a -= b; }
	friend modular operator*(modular a, const modular& b) { return a *= b; }
	friend modular operator/(modular a, const modular& b) { return a /= b; }
};
 
using mi = modular<int, MOD>;
using pmi = pair<mi,mi>;
using vmi = vector<mi>; 
using vpmi = vector<pmi>;

namespace debug {
    template < typename _T > inline void _debug(const char *s, _T x) { cerr << s << " = " << x << "\n"; }
    template < typename _T, typename... args > void _debug(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _debug(s + 1, a...); }
    
    #ifdef LOCAL
        #define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__)
        #define cerr cout
    #else
        #define debug(...) 1999
        #define cerr if(0) cout
    #endif
} // namespace debug
using namespace debug;

//////////////_________CODE_________//////////////

int main() {
    BOOST;
    int n; ll m; re(n, m);
	vll a(n); re(a);

	vll val;
	if(m <= 1000000) {
		FOR(i, m + 1) {
			val.PB(i);
		}
	} else {
		int poz = 63 - __builtin_clzll(m);

		ll pel = (1ll << poz) - 1;
		FOR(d, 2) {
			TRAV(i, val) i ^= pel;

			int roz = (d + 1) * 700000;
			function<void(int, int, ll)> gen = [&](int cnt, int u, ll x) {
				if(SZ(val) > roz) return;
				if(cnt == 0) {
					val.PB(x);
					return;
				}
				
				FOR(i, u, poz) {
					gen(cnt - 1, i + 1, x + (1ll << i));
				}
			};

			FOR(i, 0, poz + 1) {
				gen(i, 0, 0ll);
				if(SZ(val) > roz) {
					break;
				}
			}

		}
		val.PB(m);

		SORT(val);
		val.resize(unique(ALL(val)) - val.begin());
	}

	vvll dp(n, vll(SZ(val), -LLINF));
	
	FOR(i, n) {
		ll best = -LLINF;
		if(i == 0) best = 0;
		
		FOR(j, SZ(val)) {
			setmax(dp[i][j], best + a[i] * (1ll * __builtin_popcountll(val[j])));

			if(i > 0) {
				setmax(best, dp[i - 1][j]);
			}
		}
	}

	ll res = -LLINF;
	FOR(i, 0, SZ(val)) {
		setmax(res, dp[n - 1][i]);
	}
	prln(res);
}