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
#include<bits/stdc++.h>
using namespace std;
using lld = long long;

const lld MAXN = 200;
const lld MAXM = 60;
const lld INF = 3e18;

lld dp[MAXM+5][MAXN+5][MAXN+5];
lld dp2[MAXM+5][MAXN+5][MAXN+5];
vector<lld> a;

lld S(lld b, lld e){
	return a[e]-a[b-1ll];
}

lld calc(lld m, lld b){
	m &= (1ll<<b)-1ll;
	m--;
	lld res=60;
	while(res > 0 && !(m&(1ll<<res)))
		res--;
	return max((lld) __builtin_popcount(m),res-1ll);
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	lld n;
	lld m;
	cin >> n >> m;
	m++;

	a.resize(n+1ll);
	for(lld i=1ll;i<=n;i++)
		cin >> a[i];

	for(lld i=1ll;i<=n;i++)
		a[i] += a[i-1ll];

	for(lld i=0;i<=MAXM;i++)
		for(lld j=1ll;j<=n;j++)
			for(lld k=j;k<=n;k++)
				dp2[i][j][k] = dp[i][j][k] = -INF;

	bool ok = false;
	for(lld b=0;b<=MAXM;b++)
		for(lld i=1ll;i<=n;i++){
			dp[b][i][i] = max(0ll, (lld) b * S(i,i));
			dp2[b][i][i] = (!ok ? -INF : max(0ll, calc(m,b) * S(i,i)));
			if(m&(1ll<<(b-1ll)))
				ok = true;
		}

	for(lld b=1ll;b<=MAXM;b++){
		for(lld i=1ll;i<=n;i++)
			for(lld j=i+1ll;j<=n;j++)
				dp[b][i][j] = dp[b-1ll][i][j];

		for(lld i=1ll;i<=n;i++)
			for(lld k=i;k<n;k++)
				for(lld j=k+1ll;j<=n;j++)
					dp[b][i][j] = max(dp[b][i][j], dp[b-1ll][i][k] + dp[b-1ll][k+1ll][j] + S(k+1ll,j));
	}

	for(lld b=1ll;b<=MAXM;b++){
		for(lld i=1ll;i<=n;i++)
			for(lld j=i;j<=n;j++)
				dp2[b][i][j] = max(dp2[b][i][j], dp2[b-1ll][i][j]);

		if(m&(1ll<<(b-1ll))){
			for(lld i=1ll;i<=n;i++)
				for(lld j=i;j<=n;j++)
					dp2[b][i][j] = max(dp2[b][i][j], dp[b-1ll][i][j]);

			for(lld i=1ll;i<=n;i++)
				for(lld k=i;k<n;k++)
					for(lld j=k+1ll;j<=n;j++)
						dp2[b][i][j] = max(dp2[b][i][j], dp[b-1ll][i][k] + dp2[b-1ll][k+1ll][j] + S(k+1ll,j));
		}
	}

	cout << dp2[MAXM][1ll][n] << "\n";

	return 0;
}