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
#include <iostream>
#include <algorithm>
#include <vector>
//#include <bitset>
#include <climits>

using tab = std::vector<long long>;
//using uint64_t = uint_least64_t;


inline uint64_t get_n_bits(uint64_t i) {
	i = i - ((i >> 1) & 0x5555555555555555);
	i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
	return (((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56;
}

inline long long get_a(const uint64_t n, const uint64_t m, const tab& as) {
	tab sums(n + 1, LLONG_MIN);
	sums[0] = 0ul;
	for (uint64_t t = m;; --t) {
		const uint64_t beg = std::min(n, m - t + 1);
		const uint64_t end = n < t + 1 ? 0ull : n - t - 1;
		const long long n_bits = get_n_bits(t);
		for (uint64_t i = beg; i > end; --i) {
			const long long new_sum = sums[i - 1] + n_bits * as[n - i];
			if (new_sum > sums[i]) sums[i] = new_sum;
		}
		if (t == 0) break;
	}
	return sums.back();
}

int main()
{
	uint64_t n, m;
	std::cin >> n >> m;
	tab as(n);
	for (int i = 0; i < n; ++i) std::cin >> as[i];
	std::cout << get_a(n, m, as);
}