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
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = ll(1e18) * 3LL;

int n;
ll m;
ll a[207];
ll pref[207];
ll mem[207][207][2][67];
bool vis[207][207][2][67];

// t:
// 0 - 2^k-1
// 1 - k ostatnich cyfr m
ll calc(int a, int b, int t, int k) {
	if(vis[a][b][t][k])
		return mem[a][b][t][k];
		
	if(b < a)
		return 0;
	if(k == -1) {
		if(a == b)
			return 0;
		else
			return -INF;
	}
		
	vis[a][b][t][k] = 1;
	mem[a][b][t][k] = -INF;
	
	int l = k - 1;
	while(l >= 0 && !(m & (1LL << l))) l--;
	
	for(int d = a - 1 ; d <= b ; d++) {
		ll tmp = calc(a, d, 0, k - 1);
		if(t == 0)
			tmp += calc(d + 1, b, 0, k - 1);
		else
			tmp += calc(d + 1, b, 1, l);
		tmp += pref[b] - pref[d];
		mem[a][b][t][k] = max(mem[a][b][t][k], tmp);
	}
	
	return mem[a][b][t][k];
}

int main() {
	scanf("%d%lld", &n, &m);
	for(int i = 1 ; i <= n ; i++) {
		scanf("%lld", &a[i]);
		pref[i] = pref[i - 1] + a[i];
	}
		
	int x = 61;
	while(x >= 0 && !(m & (1LL << x))) x--;
	printf("%lld\n", calc(1, n, 1, x)); 
		
	return 0;
}