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
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
#define pb push_back
#define mp make_pair
#define dd second
#define ff first
#define sz size()
#define For(i,s,a) for(lld i=(lld)s;i<(lld)a;++i)

lld lim = 1e18 + 1;

lld nex(lld x, int bits){
	if(x<-1)return -2;
	++x;
	while(__builtin_popcountll(x) > bits)
	{
		if(x>lim)return -2;
		if(x<0)return -2;
		x |= x-1;
		++x;
	}
	
	for(lld i = bits - __builtin_popcountll(x); i>0; --i)	
	{
		if(x>lim)return -2;
		if(x<0)return -2;
		x |= x+1;
	}
	if(x>lim)return -2;
	return x;
}

vector<pll>dp[2];

// pary : liczba, zysk

bool worse(pll a, pll b){
	if(a.ff >= b.ff && a.dd<=b.dd)return 1;
	return 0;
}

int32_t main(void){
	lld wyn = -lim;
	dp[0].pb(mp(-1,0));
	int a;
	lld b;
	scanf("%d%lld", &a,&b);
	lim = b;
	For(i,1,a+1){
		lld g;
		scanf("%lld",&g);
		int x = i&1;
		int pr = x ^ 1;
		sort(dp[pr].begin(),dp[pr].end());
		//for(auto xd:dp[pr])cout<<xd.ff<<" "<<xd.dd<<"   ";puts("");
		for(int j = dp[pr].sz-2; j>=0; --j){
			if(worse(dp[pr][j], dp[pr][j+1]))
			dp[pr][j] = dp[pr][j+1];
		}
		//for(auto xd:dp[pr])cout<<xd.ff<<" "<<xd.dd<<" a  ";puts("");
		dp[x].clear();
		dp[pr].erase(unique(dp[pr].begin(), dp[pr].end()), dp[pr].end());
		lld tmp = -2;
		For(j,0,61){
			tmp = -2;
			For(k,0,dp[pr].sz){
				if(tmp <= dp[pr][k].ff)
				tmp = nex(dp[pr][k].ff, j);
				if(tmp == -2)break;
		//		cout<<i<<" "<<dp[pr][k].ff<<" "<<j<<" "<<tmp<<"   "<<dp[pr][k].dd<<" "<<__builtin_popcountll(tmp)<<" "<<g<<"   "<<dp[pr][k].dd + __builtin_popcountll(tmp) * g<<endl;
				dp[x].pb( mp( tmp, dp[pr][k].dd + __builtin_popcountll(tmp) * g) );
				if(i == a)
				wyn = max(wyn, dp[x].back().dd);
			}
		}
	}
	printf("%lld\n",wyn);
}