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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<algorithm>
#include<iostream>
#include<vector>
#include<utility>

#define REP(i, n) for(int i=0; i<(n); i++)
#define FOR(i, a, b) for(int i=(a); i <= (b); i++)

using namespace std;

typedef long long llint;

const int MAX_N = 200;
const int MAX_C = 63; // 3;  // 63

llint aa[1 + MAX_N];

vector<llint> bb0, qq0;

int xx[MAX_C];

vector<pair<llint, llint> > bbqq;

llint next_b(llint b0, int c1, llint m) {
  int c0;
  llint b1 = b0 + 1; c0 = 0;
  REP(i, MAX_C) { xx[i] = b1 & 1; b1 >>= 1; if (xx[i]) c0++; }
  b1 = b0 + 1;
  if (c1 == c0) return b1;
  if (c1 < c0) {
    int num_1 = 0;
    REP(i, MAX_C) {
      if (xx[i] == 0) {
        if (num_1 >= 1 + c0 - c1) {
          xx[i] = 1; c0++; b1 |= 1ll << i;
          // cout << "QQ b1=" << b1 << endl;
          REP(j, i) if (xx[j]) {
            xx[j] = 0; c0--; b1 -= 1ll << j;
          }
          REP(j, c1-c0) {
            xx[j] = 1; c0++; b1 |= 1ll << j;
          }
          return b1;
        }
        // num_1 = 0;
      } else {
        num_1++;
      }
    }
  }
  if (c1 == c0) return b1;
  if (c1 > c0) {
    REP(i, MAX_C) {
      if (xx[i] == 0) {
        xx[i] = 1; c0 += 1; b1 |= 1ll << i;
        if (c0 == c1) return b1;
      }
    }
  }
  return -2;
}

llint next_b_slow(llint b0, int c1, llint m) {
  // optimize this
  FOR(b, b0 + 1, m) {
    int c = 0;
    llint b2 = b;
    while (b2 > 0) {
      c += b2 & 1;
      b2 >>= 1;
    }
    if (c == c1) {
      return b;
    }
  }
  return -2;
}

int main(void) {
  int n;
  llint m;
  cin >> n >> m;
  FOR(i, 1, n) cin >> aa[i];

  bb0.push_back(-1);
  qq0.push_back(0);

  llint best;
  bool first;

  FOR(k, 1, n) {
    //cout << "k=" << k << endl;
    bbqq.clear();
    FOR(c1, 0, MAX_C) {
        // process {bb,qq} at [k-1][c0] to update at [k][c1]
        int s = bb0.size();
        REP(i, s) {
          llint b0 = bb0[i];
          llint q0 = qq0[i];
          llint b1 = -2, q1;
          // b1 = min b : b > b0, b <= m, C(b) = c1 (assume C(b0) == c0)
          b1 = next_b(b0, c1, m);
          //llint b1_s = next_b_slow(b0, c1, m);
          //if (b1 != b1_s && b1 <= m) {
          //  cout << "NEW b0="<<b0<< " c1="<<c1 << " b1="<<b1<<endl;
          //  cout << "OLD b0="<<b0<< " c1="<<c1 << " b1="<<b1_s<<endl;
          //}
          if (b1 == -2 || b1 > m) continue;

          q1 = q0 + aa[k]*c1;
          // insert {b1,q1} at [k][c1]
          //cout << "c0="<<c0<<" i="<<i<<" b0="<<b0 <<" q0="<<q0 << endl;
          //cout << "k="<<k << " c="<<c1 << " b=" << b1 << " q=" << q1 << endl;
          bbqq.push_back(make_pair(b1,q1));
        }
    }

    // discard redundant data from [k][c1]
    sort(bbqq.begin(), bbqq.end());
    bb0.clear();
    qq0.clear();
    int s1 = bbqq.size();
    llint q_level = s1 > 0 ? bbqq[0].second : -3;
    REP(i, s1) {
      llint b = bbqq[i].first;
      llint q = bbqq[i].second;
      if (i > 0 && q <= q_level) continue;
      q_level = q;
      bb0.push_back(b);
      qq0.push_back(q);
    }
    int s2 = bb0.size();
    // cout << "s1="<<s1<<" s2="<<s2<<endl;
  }

  first = true;
  int s = qq0.size();
  REP(i, s) {
    //cout << "A best="<<best << " c="<<c<<" i="<<i<<endl;
    if (first || qq0[i] > best) {
      best = qq0[i];
      //cout << "B best="<<best << " c="<<c<<" i="<<i<<endl;
      first = false;
    }
  }

  cout << best << endl;

  return 0;
}