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

#define FOR(i, a, n) for(decltype(n) i = (a), i##__ = (n); i <= i##__; i++)
#define REP(i, n) FOR(i, 0, (n)-1)
#define FORD(i, a, n) for(decltype(a) i = (a), i##__ = (n); i >= i##__; i--)
#define REPD(i, n) FORD(i, (n)-1, 0)
#define V vector
#define RS resize
#define EB emplace_back
#define ALL(X) X.begin(), X.end()
#define SZ(X) int(X.size())
#define OS ostream
#define ST first
#define ND second

using VI   = V<int>;
using VVI  = V<VI>;
using II   = pair<int, int>;
using VII  = V<II>;
using L    = long long;
using VL   = V<L>;
using VVL  = V<VL>;
constexpr L inf = 1e18;

#ifdef DEBUG
# define D(a...) a
#else 
# define D(a...)
#endif
# define I(a...) #a << ": " << a << "\n"

template<class A, class B> OS& operator<<(OS &os, pair<A, B> &X) {
    return os << "(" << X.ST << ", " << X.ND << ")";
}
template <class T> OS& operator<<(OS &os, V<T> &X){
    os << "{";
    REP(i, SZ(X))
        os << X[i] << ((i == SZ(X) - 1) ? "" : ", ");
    return os << "}";
}
template<class T> OS& operator<<(OS &os, V<V<T>> &X) {
	os << "[\n";
	for(auto &x : X)
		cout << "   " << x << "\n";
	return os << "]";
}

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

	int n, m; cin >> n >> m;
	VL a(n); REP(i, n) cin >> a[i];

	VVL dp(n + 1, VL(m + 1, -inf));
	dp[0] = VL(m + 1, 0); dp[1][0] = 0;

	FOR(i, 1, n) FOR(j, 1, m) {
		dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + __builtin_popcount(j) * a[i - 1]);
		if(dp[i][j] < -4e17)
			dp[i][j] = -inf;
	}

	D(cerr << I(dp));
	cout << dp[n][m] << "\n";
}