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

const long long INF = 2000000000000000000;
const int MAX = 202;
long long N, M, P;
int cnt;

long long pref[MAX];
long long A[MAX];
long long dp[MAX][MAX][62];
long long dp_suf[MAX][62];

void input(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(0);
	cin >> N >> M;
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}
	M++;
}

long long sum(int a, int b){
	return pref[b + 1] - pref[a];
}

void make_pref(){
	pref[0] = 0;
	for(int i = 0; i < N; i++){
		pref[i + 1] = pref[i] + A[i];
	}
}

void process(){
	make_pref();
	cnt = 0;
	P = 1;
	while(P < M){
		P *= 2;
		cnt++;
	}
	for(int k = 0; k < cnt; k++){
		for(int d = 1; d <= N; d++){
			for(int a = 0; a <= N - d; a++){
				int b = a + d - 1;
				if(k == 0){
					if(a == b){
						dp[a][b][k] = max(A[a], (long long) 0);
					} else if(b - a == 1){
						dp[a][b][k] = A[b];
					} else {
						dp[a][b][k] = -INF;
					}
				} else {
					long long RES = -INF;
					RES = max(RES, dp[a][b][k - 1] + sum(a, b));
					RES = max(RES, dp[a][b][k - 1]);
					for(int c = a + 1; c <= b; c++){
						RES = max(RES, dp[a][c - 1][k - 1] + dp[c][b][k - 1] + sum(c, b));
					}
					if(RES <= -INF/2) RES = -INF;
					dp[a][b][k] = RES;
				}
				//cout << "a = " << a << "   b = " << b << "   k = " << k << "       dp = " << dp[a][b][k] << endl;
			}
		}
	}
	for(int k = 0; k < cnt; k++){
		long long M2 = M;
		for(int x = 0; x < k; x++){
			M2 /= 2;
		}
		if(M2 % 2 == 0 && k != cnt){
			continue;
		}
		int prev = -1;
		M2 = M;
		for(int x = 0; x < k; x++){
			if(M2 % 2 == 1){
				prev = x;
			}
			M2 /= 2;
		}
		for(int a = 0; a < N; a++){
			if(prev == -1){
				if(k == 0){
					if(a == N - 1){
						dp_suf[a][k] = (long long) 0;
					} else {
						dp_suf[a][k] = -INF;
					}
				} else {
					dp_suf[a][k] = dp[a][N - 1][k - 1];
				}
			} else {
				long long RES = -INF;
				RES = max(RES, dp_suf[a][prev] + sum(a, N - 1));
				RES = max(RES, dp[a][N - 1][k - 1]);
				for(int c = a + 1; c <= N - 1; c++){
					RES = max(RES, dp[a][c - 1][k - 1] + dp_suf[c][prev] + sum(c, N - 1));
				}
				if(RES <= -INF/2) RES = -INF;
				dp_suf[a][k] = RES;
			}
			//cout << "a = " << a << "   k = " << k << "       dp = " << dp_suf[a][k] << endl;
		}
	}
	if(P == M){
		cout << dp[0][N - 1][cnt - 1] << endl;
	} else {
		cout << dp_suf[0][cnt - 1] << endl;
	}
}

int main(){
	input();
	process();
}