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
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " " << x << endl;

#define int long long // uważaj

const int N = 207, bi = 100;
const long long MIN = -4e18;

long long dp[N][N][bi]; // l, r, ile bitów do dyspozycji
long long pref[N];
long long suf[N][bi];
long long t[N];

inline long long prz(int l, int r) {
    if(l > r) return 0;
    return pref[r] - pref[l - 1];
}

int max_bit(long long x) {
    if(x == 0) return 0;
    int re = 0;
    while((1ll << re) <= x) re++;
    return re - 1;
}

long long max_cnt_bit(long long x) {
    if(x == 0) return 0;
    if(__builtin_popcountll(x + 1) == 1) {
        return max_bit(x) + 1;
    }
    else {
        return max_bit(x);
    }
}

void solve() {
    int n;
    long long m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    if(n == 1) {
        cout << max(0ll, t[1] * max_cnt_bit(m)) << endl;
        return;
    }

    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            for(int k =  0; k <= bi; k++) {
                dp[i][j][k] = MIN;
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int k = 0; k < bi; k++) {
            dp[i][i][k] = max(t[i] * k, 0ll);
        }
    }

    for(int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + t[i];
    }

    for(int k = 1; k < bi; k++) {
        for(int l = 1; l <= n; l++) {
            for(int r = l + 1; r <= n; r++) {
                dp[l][r][k] = max(dp[l][r][k - 1], dp[l][r][k - 1] + prz(l, r));
                for(int pod = l; pod < r; pod++) {
                    dp[l][r][k] = max(dp[l][r][k], dp[l][pod][k - 1] + dp[pod + 1][r][k - 1] + prz(pod + 1, r));
                }
            }
        }
    }

    int bicior = max_bit(m);

    for(int k = 0; k < bi; k++) {
        for(int i = 1; i <= n; i++) {
            suf[i][k] = MIN;
        }
    }

    suf[n][0] = 0;

    for(int k = 0; k <= bicior; k++) {
        for(int l = 1; l <= n; l++) {
            suf[l][k + 1] = suf[l][k];
        }

        if((1ll << k) & m) {
            for(int l = 1; l <= n; l++) {
                suf[l][k + 1] = max(suf[l][k] + prz(l, n), suf[l][k + 1]);
                suf[l][k + 1] = max(dp[l][n][k], suf[l][k + 1]);
                for(int pod = l; pod < n; pod++) {
                    suf[l][k + 1] = max(suf[l][k + 1], dp[l][pod][k] + suf[pod + 1][k] + prz(pod + 1, n));
                }
            }
        }
    }

    cout << suf[1][bicior + 1] << endl;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int test = 1;

	while(test--){
		solve();
	}

	return 0;
}