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

const int nax=215;
ll dp[nax][nax][66][2];
ll a[nax];
ll n,m;
ll s[nax];

bool czy[66];

ll daj(ll lo,ll hi)
{
    if(lo>hi) return 0;
    return s[hi]-s[lo-1];
}

ll reku(ll lo,ll hi,ll bb,ll wyp)
{
    //cout<<"XD"<<lo<<" "<<hi<<" "<<bb<<" "<<wyp<<endl;
    if(dp[lo][hi][bb][wyp]!=-1) return dp[lo][hi][bb][wyp];
    if(hi-lo+1>(1LL<<(bb+1))) return -1e18;
    if(lo>hi) return 0LL;
    if(bb==0)
    {
        if(wyp==0)
        {
            if(lo==hi)
            {
                if(a[lo]>0) return a[lo];
                else return 0;
            }
            else
            {
                return a[hi];
            }
        }
        else if(wyp==1)
        {
            if(czy[0]==true)
            {
                if(lo==hi)
                {
                    if(a[lo]>0) return a[lo];
                    else return 0;
                }
                else
                {
                    return a[hi];
                }
            }
            else
            {
                if(lo!=hi) return -1e18;
                return 0;
            }
        }
    }
    for(int i=lo-1;i<=hi;i++)
    {
        ll par=wyp;
        if(czy[bb]==true) par=0;
        ll lewo=reku(lo,i,bb-1,par);
        if(wyp==1 && czy[bb]==false && i!=hi) continue;
        ll prawo=daj(i+1,hi)+reku(i+1,hi,bb-1,wyp);
        dp[lo][hi][bb][wyp]=max(dp[lo][hi][bb][wyp],lewo+prawo);
    }
    //cout<<"CHUJ"<<lo<<" "<<hi<<" "<<bb<<" "<<wyp<<" "<<dp[lo][hi][bb][wyp]<<endl;
    return dp[lo][hi][bb][wyp];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=0;k<66;k++)
            {
                dp[i][j][k][0]=-1;
                dp[i][j][k][1]=-1;
            }
        }
    }
    ll t=m;
    int xd=0;
    while(t)
    {
        if(t%2==1) czy[xd]=true;
        xd++;
        t/=2;
    }
    int najw=0;
    for(int i=0;i<66;i++)
    {
        if(czy[i]==true) najw=i;
    }
    cout<<reku(1,n,najw,1);
    return 0;
}