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
88
89
90
91
92
93
94
95
96
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 61;
const int M = 201;

ll dp[N][2][M][M];

int n;
ll m;

ll a[M];
ll pref[M];

string s;

const ll inf = (ll) (1e18);

ll f(int l, int r) {
  if (l > r) return 0;
  if (!l) return pref[r];
  else return pref[r] - pref[l - 1];
}

ll calc(int i, int t, int l, int r) {
  if (dp[i][t][l][r] != -1) return dp[i][t][l][r];
  if (l > r) return 0;
  if (i == 60) {
    if (l != r) return -inf;
    return 0;
  } else {
    ll val = -inf;
    for (int x = l - 1; x <= r; x++) {
      if (1 > s[i] && !t && (x != r)) {
        continue;
      }
      ll a = calc(i + 1, ((0 < s[i]) || t), l, x);
      ll b = calc(i + 1, t, x + 1, r) + f(x + 1, r);
      val = max(val, a + b);
    }
    return dp[i][t][l][r] = val;
  }
}

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  ll ret = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    ret += a[i];
    pref[i] = ret;
  }
  for (int it = 0; it < 60; it++) {
    s += (m % 2);
    m /= 2;
  }
  for (int it = 0; it <= 60; it++) {
    for (int t = 0; t < 2; t++) {
      for (int l = 0; l <= n; l++) {
        for (int r = 0; r <= n; r++) {
          dp[it][t][l][r] = -1;
        }
      }
    }
  }
  reverse(s.begin(), s.end());
  cout << calc(0, 0, 0, n - 1) << endl;
}