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
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")

const long long inf=2e18+2137;
const int MAXN=1e6+10;

pair<long long,long long> dp[2][MAXN];

bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
    return (a.first!=b.first?a.first<b.first:(a.second>b.second));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,lg,p=1,p2,l=0;
    long long m,v,nxt,mx,b;
    cin>>n>>m;
    lg=__lg(m)+1;
    dp[0][0].first=-1;
    while(n--)
    {
        cin>>v;
        p2=0;
        for(int x=l;x<p;x++)
        {
            for(int i=0;i<=lg;i++)
            {
                nxt=dp[0][x].first;
                if(!(i==0&&nxt>=0))
                {
                    while(__builtin_popcountll(++nxt)>i)
                        nxt|=nxt-1;
                    b=1;
                    while(__builtin_popcountll(nxt)<i)
                        nxt|=b,b<<=1;
                    if(nxt<=m)
                        dp[1][p2].first=nxt,dp[1][p2].second=dp[0][x].second+(long long)i*v,p2++;
                }
            }
        }
        sort(dp[1],dp[1]+p2,cmp);
        mx=-inf;
        p=0;
        for(int i=0;i<p2;i++)
            if(dp[1][i].second>mx)
                mx=dp[1][i].second,dp[0][p].first=dp[1][i].first,dp[0][p].second=dp[1][i].second,p++;
        l=max(0,p-5000);
    }
    mx=-inf;
    for(int i=l;i<p;i++)
        mx=max(mx,dp[0][i].second);
    cout<<mx<<'\n';
}