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

typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define dbl(k, x) fixed << setprecision(k) << (x)

template < typename _T > inline void _DBG(const char *s, _T x) { cerr << s << " = " << x << "\n"; }
template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _DBG(s + 1, a...); }

#ifdef LOCAL
#define _upgrade ios_base::sync_with_stdio(0);
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define DBG(...) (__VA_ARGS__)
#define cerr if(0) cout
#endif

// ********************** CODE ********************** //

const int N = 207;
const int LG = 63;
const LL INF = LL(4e18) + 7;

int n;
LL m, T[N], pre[N], dp[LG][N][N], suf[LG][N];

inline LL sum(int l, int r)
{
    return pre[r] - pre[l - 1];
}

int main()
{
    _upgrade

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> T[i];
        pre[i] = pre[i - 1] + T[i];
    }

    for(int i = 0; i <= n + 1; i++)
    {
        for(int j = 0; j <= n + 1; j++)
        {
            if(i - 1 != j && i != j)
                dp[0][i][j] = -INF;
        }
        if(i != n + 1 && i != n)
            suf[0][i] = -INF;
    }

    for(int b = 1; b < LG; b++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = i; j <= n; j++)
            {
                dp[b][i][j] = -INF;
                for(int k = i - 1; k <= j; k++)
                {
                    dp[b][i][j] = max(dp[b][i][j], sum(k + 1, j) + dp[b - 1][i][k] + dp[b - 1][k + 1][j]);
                }
            }
        }
    }

    for(int b = 1; b < LG; b++)
    {
        int j = n;
        for(int i = 1; i <= n; i++)
        {
            suf[b][i] = -INF;
            bool one = ((m >> (b - 1)) & 1LL);
            if(one)
            {
                for(int k = i - 1; k <= j; k++)
                {
                    suf[b][i] = max(suf[b][i], sum(k + 1, j) + dp[b - 1][i][k] + suf[b - 1][k + 1]);
                }
            }
            else
            {
                suf[b][i] = suf[b - 1][i];
            }
        }
    }

    cout << suf[LG - 1][1] << "\n";

	return 0;
}