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
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 210,kax=1000*1000;
const ll INF = (ll)1e18;
int n,nr;
ll m;
vector<ll> intr;
ll a[nax];
ll dp[2][kax];

int main() {_
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	ll tmp=1; int l=1;
	while(tmp*2<=m) {
		tmp*=2;
		l++;
	}
	if(m<kax) {
		for(int i=0; i<=m; i++) {
			intr.PB(i); nr++;
		}
	} else {
	for(int b1=0; b1<l; b1++) {
		for(int b2=b1+1; b2<l; b2++) {
			for(int b3=b2+1; b3<l; b3++) {
				ll x = (1LL<<b1)|(1LL<<b2)|(1LL<<b3);
				if(x<=m) {
					intr.PB(x); nr++;
				}
				x = ((1LL<<l)-1)^x;
				if(__builtin_popcount(x)>3&&x<=m) {
					intr.PB(x); nr++;
				}
			}
			ll x = (1LL<<b1)|(1LL<<b2);
			if(x<=m) {
				intr.PB(x); nr++;
			}
			x=((1LL<<l)-1)^x;
			if(__builtin_popcount(x)>3&&x<=m) {
				intr.PB(x); nr++;
			}
		}
		ll x = (1LL<<b1);
		if(x<=m) {
			intr.PB(x); nr++;
		}
		x=((1LL<<l)-1)^x;
		if(__builtin_popcount(x)>3&&x<=m) {
			intr.PB(x); nr++;
		}
	}
	intr.PB(0); nr++;
	sort(intr.begin(),intr.end());
	if(intr.back()!=m) {
		intr.PB(m);
		nr++;
	}
	}
	for(int i=1; i<=n; i++) {
		for(int j=0; j<nr; j++) dp[i&1][j]=-INF;
		if(i==1) dp[1][0] = 0;
		for(int j=1; j<nr; j++) {
			dp[i&1][j]=max(dp[i&1][j-1],dp[1-(i&1)][j-1]+a[i]*(__builtin_popcount(intr[j])));
		}
	}
	cout<<dp[n&1][nr-1];
}