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

using namespace std;

#define int long long

template<typename T>
T &maxu(T &a, const T &b) {
	return a = max(a, b);
}

template<typename T>
T &minu(T &a, const T &b) {
	return a = min(a, b);
}

using matrix = vector<vector<int>>;

const int inf = 100'000'000'000'000 * 65 * 200;

const int maxn = 201;

int n, m;

vector<matrix> parts;

matrix sum;

matrix make_matrix(int val) {
	matrix result = vector<vector<int>>(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			result[i].push_back(val);
		}
	}
	return result;
}

matrix merge(const matrix &first_part, const matrix &second_part) {
	matrix result = first_part;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			maxu(result[i][j], second_part[i][j]);
			for (int mid = j; mid < i; mid++) {
				maxu(result[i][j], first_part[mid][j] + second_part[i][mid + 1]);
			}
		}
	}
	return result;
}

void add(matrix &part) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			part[i][j] += sum[i][j];
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	m++;
	sum = make_matrix(0);
	for (int nr = 0; nr < n; nr++) {
		int val;
		cin >> val;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				if (j <= nr && nr <= i) {
					sum[i][j] += val;
				}
			}
		}
	}

	parts.push_back(make_matrix(-inf));
	for (int i = 0; i < n; i++) {
		parts[0][i][i] = 0;
	}
	int pos = 0;
	while ((1LL << pos) < m) {
		matrix first_part = parts.back();
		matrix second_part = first_part;
		add(second_part);
		parts.push_back(merge(first_part, second_part));
		pos++;
	}

	int it = 0;
	int counted = 0;
	matrix res = make_matrix(-inf);
	cerr << pos << endl;
	while (counted < m) {
		if ((1LL << pos) <= m - counted) {
			matrix other = parts[pos];
			for (int i = 0; i < it; i++) {
				add(other);
			}
			res = merge(res, other);
			counted += (1LL << pos);
			it++;
		}

		pos--;
	}
	cerr << it << endl;

	cout << res[n - 1][0] << endl;
}