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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX 201
#define MIN -1000000000000000000
#define LL long long
#define REP(x, n) for(int x = 0; x < n; x++)
#define FOR(x, b, e) for(int x = b; x < e; x++)

	LL array[21][MAX][MAX];
	LL left_array[21][MAX][MAX];
int main(){

	int n;
	LL m, a[MAX], sum[MAX];


	LL l0 = 0;

	int pow = 0;

	LL rest, r = 1, r0=1;
	cin >> n >> m;
	m+=1;
	// if (m==0)
		// pow=0;
	while (r * 2 <= m){
		pow++;
		r *= 2;
	}
	r0=r;
	// cout<< r << " " << pow << " ";
	rest = m ;
	// cout  << rest;




	REP(x, n){
		cin >> a[x];
	}
	sum[0] = 0;

	FOR(x, 1, n+1){
		sum[x] = sum[x-1] + a[x-1];
		// cout << sum[x] << " ";
	}

	REP(x, n){
		array[0][0][x] = 0;
		array[0][1][x] = 0;
		left_array[0][0][x] = 0;
		left_array[0][1][x] = 0;
		// array[1][0][x] = 0;
		// array[1][1]
	}

	LL tail = 0;

	LL result;
	r = 2;
	FOR(i, 1, pow+2){
		
		REP(x,n){
			array[i][0][x] = 0;
			left_array[i][0][x] = 0;

		}

		// cout << "POW: " << i << endl; 
		FOR(l, 1, min((long long) n, r) + 1){
			FOR(x, 0, n - l + 1){
				// cout << "STEP: "<< l << " " << x<<endl;
				result = MIN;
				for(int offset = max(l0,  l - (r / 2)); offset <= min((long long) l, r / 2) ; offset++){
					result = max(result, array[i - 1][offset][x] + array[i - 1][l - offset][x + offset]  + (sum[x + l] - sum[x + offset]));
					// cout << offset << " " << result << " "<< array[i - 1][offset][x] << " " << array[i - 1][l - offset][x + offset]  << " " << sum[x + l] << " " << sum[x + offset] <<endl;
				}
				array[i][l][x] = result;
				// cout << i << " " << l << " " << x << " " << result << endl;
			}
			// cout<< "REST: " << rest <<endl;
			if (rest % 2 ==1){
				// rest -= 1;
				LL temp_r = (rest-1)/2, temp_i = i;
				while (temp_r>0 && temp_r % 2 == 0){
					temp_r /= 2;
					temp_i++;
				}
				if (l > tail + r/2)
					break;

				FOR(x, 0, n - l + 1){
					result = MIN;
									// cout << "STEP: "<< l << " " << x<<endl;

					for(int offset = max(l0,  l - tail); offset <= min((long long) l, r / 2) ; offset++){
						result = max(result, array[i - 1][offset][x] + left_array[i - 1][l - offset][x + offset]  + (sum[x + l] - sum[x + offset]));
						// cout << left_array[0][0][0];
						LL rr= array[i - 1][offset][x] + left_array[i - 1][l - offset][x + offset]  + (sum[x + l] - sum[x + offset]);
						// cout << offset << " " << array[i - 1][offset][x] << " " << left_array[i - 1][l - offset][x + offset] << " "<< rr << " " << sum[x + l] << " " << sum[x + offset] << " " <<temp_i <<endl;
					}
					left_array[temp_i][l][x] = result;
				}	
				
			}
		}
		if (rest % 2 ==1){
			rest -= 1;
			tail += r/2;
		}
		
		rest /= 2;
		r *= 2;
	}
	cout<<result<<endl;
	// if (r0==m)
		// cout<<array[pow+2][n-1][0]<<endl;
	// else
		// cout<<left_array[pow+2][n-1][0]<<endl;;




// 		REP(y, x+1){
// 			scanf("%d", &a);
// 			if((y+1)*(x-y+1)<=k && a < min_year)
// 				min_year = a;
// //			cout<<x<<" "<<y<<" "<<(y+1)<<" "<<x-y+1<<" "<<min_year<<endl;
// 		}
// 	}
// 	printf("%d\n", min_year);
	return 0;
}