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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int _n=(n), i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define TRACE(x) cerr << "TRACE(" #x ")" << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << endl;
typedef long long LL; typedef unsigned long long ULL;
constexpr int INF = 2000000000;
constexpr LL INFLL = LL(INF) * LL(INF);

constexpr int MAXN = 200;

int n;
LL bits_n;
LL bit_val[MAXN+1]; // [0..n]

void read_input() {
  cin >> n >> bits_n;
  ++bits_n;
  REP(i,n) cin >> bit_val[i];
  bit_val[n] = 0;
}

LL tables[2][MAXN+2][MAXN+2];

LL solve() {
  auto *table_ptr = &tables[0];
  auto *prev_ptr = &tables[1];

  {
    auto &table = *table_ptr;

    FOR(alpha, 0, n+1) FOR(beta, alpha, n+1) {
      table[alpha][beta] = beta-alpha <= 1 ? 0 : -INFLL;
    }
  }

  for(int bits=1;(1LL<<(bits-1))<=bits_n;++bits) {
    swap(prev_ptr, table_ptr);
    auto &table = *table_ptr;
    const auto &prev = *prev_ptr;

    FOR(alpha, 0, n+1) FOR(beta, alpha, n+1) {
      int min_gamma = alpha;
      int max_gamma = beta;
      LL sum_values = 0;
      if (alpha < beta && beta == n+1) {
        if (bits_n & (1LL << (bits-1))) {
          max_gamma = beta-1;
          // sum_values still 0
        } else {
          min_gamma = beta;
        }
      }
      LL best = -INFLL;
      for (int gamma = max_gamma;; --gamma) {
        LL val = sum_values + prev[alpha][gamma] + prev[gamma][beta];
        best = max(best, val);
        if (gamma <= min_gamma) break;
        sum_values += bit_val[gamma-1];
      }
      table[alpha][beta] = best;
    }
  }

  {
    const auto &table = *table_ptr;
    return table[0][n+1];
  }
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  read_input();
  LL res = solve();
  cout << res << "\n";
}