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
#include <iostream>
#include <limits>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

using I = unsigned long long;
using LL = long long;

inline int popcount(I a) {
    return __builtin_popcount(a >> 32) + __builtin_popcount(a & 0xFFFFFFFF);
}

inline I more_popcnt(I a, int l) {
    for (int i=0; i < 62; i++) {
        if (l == 0) return a;
        if(!(a & (1ull << i))) {
            a = a | (1ull << i);
            l --;
        }
    }
    abort();
}

inline I less_popcnt(I a, int to) {
    int o = popcount(a);
    if (o <= 1) return (I)-1;

    for (int i=0; i < 62; i ++) {
        if (a & (1ull << i)) {
            a += 1ull << i;
            if (popcount(a) < o)
                return a;
        }
    }

    abort();
}

I next_with_bits(I a, int bits) {
    while (true) {
        int b = popcount(a);
        if (b == bits) return a;
        else if (b < bits)
            return more_popcnt(a, bits - b);
        else
            a = less_popcnt(a, bits);
        if (a == (I)-1) return (I)-1;
    }
}

vector<pair<LL, I> > hull(vector<pair<LL, I> > pairs) {
    std::sort(pairs.begin(), pairs.end(), [](const pair<LL, I>& a, const pair<LL, I>& b) {
            return make_pair(a.second, -a.first) < make_pair(b.second, -b.first);
        });

    LL min_y = numeric_limits<LL>::min();
    vector<pair<LL, I> > r;
    for (auto p : pairs) {
        I x = p.second;
        LL y = p.first;
        if (y > min_y) {
            r.push_back(make_pair(y, x));
            min_y = y;
        }
    }

    return r;
}

LL solve(vector<LL> values, I limit) {
    vector<pair<LL, I>> solutions;
    solutions.push_back(make_pair(0,0));
    int max_popcnt = 62;

    for (LL v : values) {
        vector<pair<LL, I>> new_solutions;
        for (auto sol : solutions) {
            LL price = sol.first;
            I minbit = sol.second;
            for (int target_popcnt=0; target_popcnt < max_popcnt; target_popcnt ++) {
                I cbit = next_with_bits(minbit, target_popcnt);
                if (cbit == (I)-1) continue;
                assert(popcount(cbit) == target_popcnt);
                //cout << cbit << " " << minbit << endl;
                assert(cbit >= minbit);
                if (cbit > limit) continue;

                LL new_price = target_popcnt * v + price;
                I new_minbit = cbit+1;
                new_solutions.push_back(make_pair(new_price, new_minbit));
            }
        }

        //cerr << "presize " << new_solutions.size() << endl;
        solutions = hull(new_solutions);
        //cerr << "size " << solutions.size() << endl;
    }

    LL best_sol = numeric_limits<LL>::min();
    for (auto sol : solutions) {
        best_sol = max(sol.first, best_sol);
    }
    return best_sol;
}

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    I limit;
    cin >> n >> limit;
    vector<LL> values((size_t)n); for(LL&v:values)cin>>v;
    cout << solve(values, limit) << endl;
}