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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;

const int MAX_N = 1e6+5;
const int M = 1e6;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

int n;
ll m;
vector<ll> dp;
ll a[205];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (m > MAX_N) {
        cout << 0;
        return 0;
    }

    dp.resize(m+1, -INF);
    dp[0] = 0LL;
    for (int i = 1; i < m+1; i++) {
        dp[i] = max(dp[i-1], a[0] * __builtin_popcount(i));
    }

    for (int i = 1; i < n; i++) {
        vector<ll> tmp(m+1, -INF);
        for (int j = i; j <= m+1; j++) {
            tmp[j] = max(dp[j-1] + a[i] * __builtin_popcount(j), tmp[j-1]);
        }
        dp = tmp;
    }

    cout << dp[m];


    return 0;
}