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
#include <bits/stdc++.h>
#define ff first
#define ss second
#define INF 9223372036854775807

using namespace std;

long long n,m,t[201],h,w;
pair <long long,long long> dp[201][61];

long long next(long long a, long long c) {
	bitset <60> b(a); int l=b.count(); int h=0;
	if (c<l) {
		for (int i=0; i<60; ++i) {
			if (b[i]) {
				++h; b[i]=0;
			} else {
				if (h>=2) {b[i]=1; break;}
			}
		}
		return next((long long)b.to_ullong(),c);
	} else if (c>l) {
		for (int i=0; i<60; ++i) {
			if (!b[i] && c>l) {b.flip(i); ++l;}
		}
		return (long long)b.to_ullong();
	} else {
		return a;
	}
}

int main() {
	scanf("%lld %lld",&n,&m);
	
	for (int i=0; i<n; ++i) 
		scanf("%lld",&t[i]);

	for (long long i=0,j=0; i<=60; j+=1LL<<i,++i)
		if (j<m) dp[0][i]={i*t[0],j};
		else dp[0][i]={-INF,-1};

	for (int i=1; i<n; ++i) {
		dp[i][0]={-INF,-1};
		for (int j=1; j<=60; ++j) {
			dp[i][j]={-INF,-1};
			for (int k=0; k<=60; ++k) {
				if (dp[i-1][k].ss != -1) {
					h=next(dp[i-1][k].ss+1,j);
					if (h<=m) {
						if (dp[i][j].ff<dp[i-1][k].ff+t[i]*(long long)j) {
							dp[i][j]={dp[i-1][k].ff+t[i]*(long long)j,h};
						}
					}
				}
			}
		}
	}

	for (int i=0; i<=60; ++i) {
		w=max(w,dp[n-1][i].ff);
	}
	printf("%lld\n",w);
	return 0;
}