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
#include <bits/stdc++.h>
#define sum(a, b) prefix_sum[b] - prefix_sum[a - 1]
#define FOR_ab for(int a = 1; a < N + 1; a ++) for(int b = a; b < N + 1; b ++)
#define FOR(i, p, q) for(int i = p; i < q; i ++)
using namespace std;
typedef long long ll;
const bool deb = 0;

const ll inf = -4000000000000000000;
const int maxN = 203;
const int maxLogK = 62;
//best[a][b][n] - najlepsza piosenka od a do b wlacznie, ze wzmocnieniem <= 2^n
ll N, K, logK, quality[maxN], prefix_sum[maxN], best[maxN][maxN][maxLogK], result[maxN][maxN][maxLogK];

ll add(ll p, ll q)
{
	if(p == inf || q == inf)
		return inf;
	return p + q;
}

ll log(ll p)
{
	ll r = 0;
	while(p > 1)
	{
		p /= 2;
		r ++;
	}
	return r;
}


int main()
{
	//wczytanie danych
	scanf("%lld%lld", &N, &K);
	logK = log(K) - 1;
	FOR(i, 1, N + 1)
	{
		scanf("%lld", &quality[i]);
		//obliczenie sum czesciowych
		prefix_sum[i] = prefix_sum[i - 1] + quality[i];
	}
	
	//podstawa indukcji - wyniki dla kazdego przedzialu dla k2 <= 1
	FOR_ab
		best[a][b][0] = inf;
	FOR(a, 1, N + 1)
	{
		best[a][a][0] = max(quality[a], (ll)0);
		best[a][a + 1][0] = quality[a + 1];
	}
	
	//indukcja
	FOR(e, 1, logK + 1)
		FOR_ab
		{
			//best[a][b][n] = max(best[a][b][n - 1], best[a][i][n - 1] + best[i + 1][b][n - 1] + sum[i + 1][b])
			best[a][b][e] = best[a][b][e - 1];
			FOR(i, a, b + 1)
				best[a][b][e] = max(best[a][b][e], add(add(best[a][i - 1][e - 1], best[i][b][e - 1]), sum(i, b)));
		}
						if(deb)
						{
							FOR(e, 0, logK + 1)
							{
								printf("%d:\n", e);
								FOR(a, 1, N + 1)
								{
									FOR(b, 1, N + 1)
										printf("%lld ", best[a][b][e]);
									printf("\n");
								}
								printf("\n");
							}
							printf("\n");
						}
	
	//uwzglednienie dalszych cyfr k - dalsza indukcja
	FOR_ab
		result[a][b][0] = best[a][b][logK];
	
	ll bits_on = 1;
	FOR(e, 1, logK + 1)
	{
		if(K & (1 << (logK - e)))
		{
			FOR_ab
				result[a][b][e] = result[a][b][e - 1];
								//if(deb)
									//printf("e = %lld   BIT: %d\n", (int)(K & (1 << (logK - e))));
		}
		else
		{
			FOR_ab
			{
				result[a][b][e] = result[a][b][e - 1];
				FOR(i, a, b + 2)
					result[a][b][e] = max(result[a][b][e],
					add(add(result[a][i - 1][e - 1], best[i][b][e - 1]), bits_on * sum(i, b)));
			}
			bits_on ++;
		}
	}
	
	printf("%lld\n", max(result[1][N][0], (ll)0));
	return 0;
}