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
116
117
118
119
#include <iostream>
#include<vector>
using namespace std;
const int mx = 205;
int n, wsk,wsk2;
long long poz;
long long m, wyn;
long long t[mx];
struct dane {
	long long poc, dp;
};
vector<dane>poprz, akt;
int ile_bitow(long long x) {
	int ile = 0;
	while (x>0) {
		if (x & 1 == 1)++ile;
		x >>= 1;
	}
	return ile;
}
long long wiecej(long long x) {
	int przes = 0;
	long long w = 1;
	while (((x >> przes) & 1) == 1) {
		++przes;
		w *= 2;
	}
	x += w;
	return x;
}
long long mniej(long long x) {
	int przes = 0;
	while ((x & 1) == 0) {
		++przes;
		x >>= 1;
		if(x==0)return 1e18;
	}
	++przes;
	x >>= 1;
	while ((x & 1) == 0) {
		++przes;
		x >>= 1;
		if(x==0)return 1e18;
	}
	++przes;
	x >>= 1;
	while ((x & 1) == 1) {
		++przes;
		x >>= 1;
	}
	++x;
	x <<= przes;
	return x;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i<n; ++i) {
		cin >> t[i];
	}
	if (t[0] <= 0) {
		akt.push_back({ 0,0 });
	}
	else {
		poz = 0;
		while (poz <= m) {
			akt.push_back({ poz,t[0]*ile_bitow(poz) });
			poz = wiecej(poz);
		}
	}
	for (int i = 1; i<n; ++i) {
		poprz.clear();
		for (int j = 0; j<akt.size(); ++j) {
			poprz.push_back(akt[j]);
		}
		akt.clear();
		poz = i;
		wsk2 = 0;
		int ps = poprz.size();
		while (wsk2 + 1 < ps&&poprz[wsk2 + 1].poc < poz) {
			++wsk2;
		}
		int z = ile_bitow(poz);
		wyn = poprz[wsk2].dp + t[i] * z;
		akt.push_back({ poz,wyn });
		for (;;) {
			long long nast, nast2;
			if (t[i] >= 0) {
				nast = wiecej(poz);
			}
			else {
				nast = mniej(poz);
			}
			if (wsk2 + 1<ps) {
				nast2 = poprz[wsk2 + 1].poc+1;
				if (nast2<nast) {
					poz = nast2;
				}
				else {
					poz = nast;
				}
			}
			else {
				poz = nast;
			}
			if (poz>m)break;
			while (wsk2 + 1 < ps&&poprz[wsk2 + 1].poc < poz) {
				++wsk2;
			}
			wyn = poprz[wsk2].dp + t[i] * ile_bitow(poz);
			if (wyn>akt.back().dp) {
				akt.push_back({ poz,wyn });
			}
		}
	}
	cout << akt.back().dp;
	return 0;
}