stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/*|In The Name Of Allah|*/



#include <bits/stdc++.h>



using namespace std;



const int N = 111;

const int M = 11;



int n;

int k;

int v[N];

int mem[N][N][N];



int go(int l , int r , int stp){

    if(stp < 0)

        return -1e9;

    if(l > r || stp == 0)

        return 0;

    if(~mem[l][r][stp])

        return mem[l][r][stp];

    int ret = 0;

    int c1 , c2 , c3 , c4;

    c1 = go(l + 1 , r , stp - 1) + v[l];

    c2 = go(l , r - 1 , stp - 1) + v[r];

    c3 = go(l + 1 , r , stp - 2);

    c4 = go(l , r - 1 , stp - 2);

    return mem[l][r][stp] = max(0 , max(max(c1 , c2) , max(c3 , c4)));

}



int main(){

    scanf("%d%d" , &n , &k);

    for(int i = 1; i <= n; i++){

        scanf("%d" , &v[i]);

    }

    memset(mem , -1 , sizeof mem);

    printf("%d\n" , max(go(1 , n , k) , 0));

}


// Faster C++ solution for the same problem (measured speedup: 6.511989295726825x):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define LL long long

#define Max(a,b) (a>b?a:b)

using namespace std;

const int MAXN = 55;

LL A[MAXN], K1, K, N, ans=0;



int main()

{

	cin>>N>>K1;

	LL i, j, l, r, fang, na;

	for(i=1;i<=N;i++) scanf("%lld", &A[i]);

	for(K=0;K<=K1;K++) {

		for(l=0;l<=K;l++) {

			for(r=0;r<=K-l && l+r<=N;r++) {

				vector<int> V;

				for(i=1;i<=l;i++) V.push_back(A[i]);

				for(j=0;j<r;j++) V.push_back(A[N-j]);

				sort(V.begin(), V.end());

				LL num = 0;

				fang = K-l-r;

				for(i=fang;i<V.size();i++) {

					num+=V[i];

				}

				ans = Max(ans, num);

			}

		}

	}

	printf("%lld\n", ans);

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#define N 110

using namespace std;

int a[N],dp[N][N][N],n,m;

int main(){

	memset(dp,-128/3,sizeof(dp));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]); 

	dp[0][n+1][0]=0;

	for(int i=0;i<=n+1;i++)

		for(int j=n+1;j>i;j--)

			for(int k=0;k<=m;k++){

				dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+a[i+1]);

				dp[i][j-1][k+1]=max(dp[i][j-1][k+1],dp[i][j][k]+a[j-1]);

				if(a[i+1]<0)

					dp[i+1][j][k+2]=max(dp[i+1][j][k+2],dp[i][j][k]);

				if(a[j-1]<0)

					dp[i][j-1][k+2]=max(dp[i][j-1][k+2],dp[i][j][k]);

			}

	int ans=0;

	for(int i=0;i<=n;i++)

		for(int j=i+1;j<=n+1;j++)

			for(int k=0;k<=m;k++)

				ans=max(ans,dp[i][j][k]);

	cout<<ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 6.369537627927299x):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define LL long long

#define Max(a,b) (a>b?a:b)

using namespace std;

const int MAXN = 55;

LL A[MAXN], K1, K, N, ans=0;



int main()

{

	cin>>N>>K1;

	LL i, j, l, r, fang, na;

	for(i=1;i<=N;i++) scanf("%lld", &A[i]);

	for(K=0;K<=K1;K++) {

		for(l=0;l<=K;l++) {

			for(r=0;r<=K-l && l+r<=N;r++) {

				vector<int> V;

				for(i=1;i<=l;i++) V.push_back(A[i]);

				for(j=0;j<r;j++) V.push_back(A[N-j]);

				sort(V.begin(), V.end());

				LL num = 0;

				fang = K-l-r;

				for(i=fang;i<V.size();i++) {

					num+=V[i];

				}

				ans = Max(ans, num);

			}

		}

	}

	printf("%lld\n", ans);

	return 0;

}
// Slower C++ solution:
/*|In The Name Of Allah|*/



#include <bits/stdc++.h>



using namespace std;



const int N = 111;

const int M = 11;



int n;

int k;

int v[N];

int mem[N][N][N];



int go(int l , int r , int stp){

    if(stp < 0)

        return -1e9;

    if(l > r || stp == 0)

        return 0;

    if(~mem[l][r][stp])

        return mem[l][r][stp];

    int ret = 0;

    int c1 , c2 , c3 , c4;

    c1 = go(l + 1 , r , stp - 1) + v[l];

    c2 = go(l , r - 1 , stp - 1) + v[r];

    c3 = go(l + 1 , r , stp - 2);

    c4 = go(l , r - 1 , stp - 2);

    return mem[l][r][stp] = max(0 , max(max(c1 , c2) , max(c3 , c4)));

}



int main(){

    scanf("%d%d" , &n , &k);

    for(int i = 1; i <= n; i++){

        scanf("%d" , &v[i]);

    }

    memset(mem , -1 , sizeof mem);

    printf("%d\n" , max(go(1 , n , k) , 0));

}


// Faster C++ solution for the same problem (measured speedup: 6.245293934698849x):
#include <bits/stdc++.h>

#include <fstream>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>





typedef  long long ll;

typedef long double ld;

using namespace std;

using namespace __gnu_pbds;





#define endl "\n"

#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N=2e5+5;

ll mod=1e9+7;



ll mul (ll a, ll b)

{

    a%=mod;

    b%=mod;

    return (a*b)%mod;

}

ll add (ll a, ll b)

{

    a%=mod;

    b%=mod;

    return (a+b+mod)%mod;

}

ll fastpow(ll b, ll p)

{

    if(p==0)

        return 1;

    ll ans=fastpow(b,p/2);

    ans=mul(ans,ans);

    if(p%2)ans=mul(ans,b);

    return ans;

}

int n,k;

ll solve(deque<ll>&qq)

{

    ll ans=0;



    for(int i=0; i<=n; i++)

    {

        for(int j=0; j<=n; j++)

        {





            deque<ll>q=qq;

            priority_queue<int,vector<int>,greater<int>>pq;

            int co=k;

            for(int x=0; x<i&&q.size(); x++)

            {

                co--;

                pq.push(q.front());

                q.pop_front();

            }

            for(int x=0; x<j&&q.size(); x++)

            {

                co--;

                pq.push(q.back());

                q.pop_back();

            }

            if(co<0)

            {

                continue;

            }

            while(co>0&&pq.size())

            {

                if(pq.top()<0)

                    pq.pop();

                else

                    break;

                co--;



            }

            if(co<0)

                continue;

            ll total=0;

            while(pq.size())

                total+=pq.top(),pq.pop();

          ///  cout<<"i= "<<i<<" j= "<<j<<" total= "<<total<<endl;

            ans=max(ans,total);

        }



    }





    return ans;

}



int main()

{

    FIO

    cin>>n>>k;

    deque<ll>q1,q2;

    for(int i=0; i<n; i++)

    {

        int x;

        cin>>x;

        q1.push_back(x);

        q2.push_front(x);

    }

    cout<<max(solve(q1),solve(q2));





    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#define N 110

using namespace std;

int a[N],dp[N][N][N],n,m;

int main(){

	memset(dp,-128/3,sizeof(dp));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]); 

	dp[0][n+1][0]=0;

	for(int i=0;i<=n+1;i++)

		for(int j=n+1;j>i;j--)

			for(int k=0;k<=m;k++){

				dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+a[i+1]);

				dp[i][j-1][k+1]=max(dp[i][j-1][k+1],dp[i][j][k]+a[j-1]);

				if(a[i+1]<0)

					dp[i+1][j][k+2]=max(dp[i+1][j][k+2],dp[i][j][k]);

				if(a[j-1]<0)

					dp[i][j-1][k+2]=max(dp[i][j-1][k+2],dp[i][j][k]);

			}

	int ans=0;

	for(int i=0;i<=n;i++)

		for(int j=i+1;j<=n+1;j++)

			for(int k=0;k<=m;k++)

				ans=max(ans,dp[i][j][k]);

	cout<<ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 6.108676305815474x):
#include <bits/stdc++.h>

#include <fstream>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>





typedef  long long ll;

typedef long double ld;

using namespace std;

using namespace __gnu_pbds;





#define endl "\n"

#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N=2e5+5;

ll mod=1e9+7;



ll mul (ll a, ll b)

{

    a%=mod;

    b%=mod;

    return (a*b)%mod;

}

ll add (ll a, ll b)

{

    a%=mod;

    b%=mod;

    return (a+b+mod)%mod;

}

ll fastpow(ll b, ll p)

{

    if(p==0)

        return 1;

    ll ans=fastpow(b,p/2);

    ans=mul(ans,ans);

    if(p%2)ans=mul(ans,b);

    return ans;

}

int n,k;

ll solve(deque<ll>&qq)

{

    ll ans=0;



    for(int i=0; i<=n; i++)

    {

        for(int j=0; j<=n; j++)

        {





            deque<ll>q=qq;

            priority_queue<int,vector<int>,greater<int>>pq;

            int co=k;

            for(int x=0; x<i&&q.size(); x++)

            {

                co--;

                pq.push(q.front());

                q.pop_front();

            }

            for(int x=0; x<j&&q.size(); x++)

            {

                co--;

                pq.push(q.back());

                q.pop_back();

            }

            if(co<0)

            {

                continue;

            }

            while(co>0&&pq.size())

            {

                if(pq.top()<0)

                    pq.pop();

                else

                    break;

                co--;



            }

            if(co<0)

                continue;

            ll total=0;

            while(pq.size())

                total+=pq.top(),pq.pop();

          ///  cout<<"i= "<<i<<" j= "<<j<<" total= "<<total<<endl;

            ans=max(ans,total);

        }



    }





    return ans;

}



int main()

{

    FIO

    cin>>n>>k;

    deque<ll>q1,q2;

    for(int i=0; i<n; i++)

    {

        int x;

        cin>>x;

        q1.push_back(x);

        q2.push_front(x);

    }

    cout<<max(solve(q1),solve(q2));





    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define LL long long

using namespace std;

int f[55][105], g[55][105], v[105];

int main(){

    ios::sync_with_stdio(false);

    int n, k; cin>>n>>k;

    for(int i = 1; i <= n; i++) cin>>v[i];

    for(int i = 0; i <= 51; i++){

        for(int j = 0; j <= 101; j++)

            f[i][j] = g[i][j] = -1e9;

    }

    f[0][k] = 0;

    for(int i = 0; i <= n - 1; i++){

        for(int j = k; j >= 1; j--){

            f[i + 1][j - 1] = max(f[i + 1][j - 1], f[i][j] + v[i + 1]);

            if(j >= 2) f[i + 1][j - 2] = max(f[i + 1][j - 2], f[i][j]);

        }

    }

    g[n + 1][k] = 0;

    for(int i = n + 1; i >= 2; i--){

        for(int j = k; j >= 1; j--){

            g[i - 1][j - 1] = max(g[i - 1][j - 1], g[i][j] + v[i - 1]);

            if(j >= 2) g[i - 1][j - 2] = max(g[i - 1][j - 2], g[i][j]);

        }

    }

    int ans = 0;

    for(int i = 0; i <= n; i++){

        for(int j = i + 1; j <= n + 1; j++){

            for(int K = i; K <= k && K <= 2 * i; K++){

                for(int t = n - j + 1; t + K <= k; t++){

                    ans = max(f[i][k - K] + g[j][k - t], ans);

                }

            }

        }

    }

    cout<<ans;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1225930633052246x):
#include <cstdio>

#include <cstdlib>

#include <vector>

#include <queue>



using namespace std;



int main() {

    int n, k;

    scanf("%d%d", &n, &k);

    // 建立羊肉串

    vector<int> array(n);

    for (int i = 0; i< n; i++) {

        scanf("%d", &array[i]);

    }



    // 开始枚举

    int maxl = 0;

    for (int a = 0; a <= k; a++) {

        for (int b = 0; b <= k; b++) {

            for (int c = 0; c <= k; c++) {

                if (a+b+c <= k && a+b >= c && a + b <= n) {

                    // 操作合理

                    priority_queue<int> qu;

                    for (int i = 0; i < a; i++) {

                        qu.push(array[i]);

                    }

                    for (int i = 0; i < b; i++) {

                        qu.push(array[n - i - 1]);

                    }

                    int sum = 0;

                    for (int i = 0; i < a + b - c; i++) {

                        sum += qu.top();

                        qu.pop();

                    }

                    maxl = max(maxl, sum);

                }

            }

        }



    }

    printf("%d\n", maxl);

    return EXIT_SUCCESS;

 }
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define ll long long



const int N = 1e6+3,M=55;



const ll oo=1e18;



int n,m,ans,tc,a[N],b[N],k;



#define f first



#define s second



const int dx[]={0,0,1,-1},

          dy[]={1,-1,0,0};



char s[N];



ll dp[105][105][105];



ll solve(int l,int r,int rem){

    if (rem<0)

        return -1e9;

    if (l>r)

        return 0;

    ll &ret = dp[l][r][rem];

    if (ret!=-oo)

        return ret;

    ret=0;

    ret=max(ret,max(a[l]+solve(l+1,r,rem-1),solve(l+1,r,rem-2)));

    return ret=max(ret,max(a[r]+solve(l,r-1,rem-1),solve(l,r-1,rem-2)));

}



int main(){

    for(int i=0;i<105;i++)

        for(int j=0;j<105;j++)

            for(int k=0;k<105;k++)

                dp[i][j][k]=-oo;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++)

        scanf("%d",&a[i]);

    printf("%lld",solve(0,n-1,k));

}






// Faster C++ solution for the same problem (measured speedup: 10.461360827417014x):
#include <bits/stdc++.h>



using namespace std;



int main() {

    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);



    int n , k;

    cin >> n >> k;



    vector<int> a(n);

    for (int i = 0 ;i < n ;i++)

        cin >> a[i];





    int ans = 0;

    for (int i = 0 ;i <= n ;i++) {

        for (int j = i ;j < n ;j++) {

            int c = i + n - j - 1;

            if (c > k) continue;

            int s = 0;

            priority_queue<int> q;



            for (int k = 0 ;k < n ;k++) {

                if (k < i || k > j) {

                    s += a[k];

                    if (a[k] < 0)

                        q.push(-a[k]);

                }

            }



            int rem = k - c;

            while (rem > 0 && q.size()) {

                s += q.top();

                q.pop();

                rem--;

            }



            ans = max(ans , s);

        }

    }



    if (n <= k) {

        int s = 0;

        priority_queue<int> q;

        for (int i = 0 ;i < n ;i++) {

            s += a[i];

            if (a[i] < 0)

                q.push(-a[i]);

        }



        int rem = k - n;

        while (rem > 0 && q.size()) {

            s += q.top();

            q.pop();

            rem--;

        }



        ans = max(ans , s);

    }



    cout << ans;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define ll long long



const int N = 1e6+3,M=55;



const ll oo=1e18;



int n,m,ans,tc,a[N],b[N],k;



#define f first



#define s second



const int dx[]={0,0,1,-1},

          dy[]={1,-1,0,0};



char s[N];



ll dp[105][105][105];



ll solve(int l,int r,int rem){

    if (rem<0)

        return -1e9;

    if (l>r)

        return 0;

    ll &ret = dp[l][r][rem];

    if (ret!=-oo)

        return ret;

    ret=0;

    ret=max(ret,max(a[l]+solve(l+1,r,rem-1),solve(l+1,r,rem-2)));

    return ret=max(ret,max(a[r]+solve(l,r-1,rem-1),solve(l,r-1,rem-2)));

}



int main(){

    for(int i=0;i<105;i++)

        for(int j=0;j<105;j++)

            for(int k=0;k<105;k++)

                dp[i][j][k]=-oo;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++)

        scanf("%d",&a[i]);

    printf("%lld",solve(0,n-1,k));

}






// Faster C++ solution for the same problem (measured speedup: 10.496709792894626x):
#include <bits/stdc++.h>



#define mem(f, v) memset(f,v,sizeof(f))

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);



typedef long long ll;

const int maxn = 100010;

const int inf = ~(1u << 31u);

const ll linf = (~(1llu << 63u)) >> 2;



using namespace std;



ll f[110][55][55];

ll d[55];



int main() {

    ios::sync_with_stdio(false);

    int n, k;

    cin >> n >> k;

    for(int i = 1; i <= n; i ++) cin >> d[i];



    for(int i = 0; i <= k; i ++){

        for(int j = 0; j <= n; j ++){

            for(int l = 0; l <= n; l ++){

                f[i][j][l] = -linf;

            }

        }

    }

    f[0][1][n] = 0;

    ll res = -linf;

    for(int i = 1; i <= k; i ++){

        for(int l = 1; l <= n; l ++){

            for(int r = n; r >= l - 1; r --){

                if(i >= 2 && l-1 >= 1) f[i][l][r] = max(f[i][l][r], f[i-2][l-1][r]);

                if(i >= 2 && r+1 <= n) f[i][l][r] = max(f[i][l][r], f[i-2][l][r+1]);

                if(l-1 >= 1 && f[i-1][l-1][r] != -linf) f[i][l][r] = max(f[i][l][r], f[i-1][l-1][r] + d[l-1]);

                if(r+1 <= n && f[i-1][l][r+1] != -linf) f[i][l][r] = max(f[i][l][r], f[i-1][l][r+1] + d[r+1]);

                res = max(res, f[i][l][r]);

            }

        }

    }

    cout << max(0ll, res) << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define ll long long



const int N = 1e6+3,M=55;



const ll oo=1e18;



int n,m,ans,tc,a[N],b[N],k;



#define f first



#define s second



const int dx[]={0,0,1,-1},

          dy[]={1,-1,0,0};



char s[N];



ll dp[105][105][105];



ll solve(int l,int r,int rem){

    if (rem<0)

        return -1e9;

    if (l>r)

        return 0;

    ll &ret = dp[l][r][rem];

    if (ret!=-oo)

        return ret;

    ret=0;

    ret=max(ret,max(a[l]+solve(l+1,r,rem-1),solve(l+1,r,rem-2)));

    return ret=max(ret,max(a[r]+solve(l,r-1,rem-1),solve(l,r-1,rem-2)));

}



int main(){

    for(int i=0;i<105;i++)

        for(int j=0;j<105;j++)

            for(int k=0;k<105;k++)

                dp[i][j][k]=-oo;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++)

        scanf("%d",&a[i]);

    printf("%lld",solve(0,n-1,k));

}






// Faster C++ solution for the same problem (measured speedup: 10.811252642073375x):
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

#define inl inline

#define re register

#define MAXN 10100

using namespace std;

int n,k;

int v[54];

int ans;int g[55];

int work(int l,int r)

{

	int cnt=k;

	if(l+r>k)return 0;

	int ind=0;

	for(int i=1;i<=l;i++)g[++ind]=v[i];

	for(int i=n;i>=n-r+1;i--)g[++ind]=v[i];

	sort(g+1,g+ind+1);

	cnt-=ind;

	int t=1;

	for(int i=1;i<=ind;i++)

	{

		if(g[i]<0&&cnt>0)

			cnt--,t++;

	}

	int tmp=0;

	for(;t<=ind;t++)tmp+=g[t];

	return tmp;

}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)scanf("%d",&v[i]);

	for(int l=0;l<=n;l++)

		for(int r=0;r<=n-l;r++)

		{

			ans=max(ans,work(l,r));

		}

	cout<<ans;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define ll long long



const int N = 1e6+3,M=55;



const ll oo=1e18;



int n,m,ans,tc,a[N],b[N],k;



#define f first



#define s second



const int dx[]={0,0,1,-1},

          dy[]={1,-1,0,0};



char s[N];



ll dp[105][105][105];



ll solve(int l,int r,int rem){

    if (rem<0)

        return -1e9;

    if (l>r)

        return 0;

    ll &ret = dp[l][r][rem];

    if (ret!=-oo)

        return ret;

    ret=0;

    ret=max(ret,max(a[l]+solve(l+1,r,rem-1),solve(l+1,r,rem-2)));

    return ret=max(ret,max(a[r]+solve(l,r-1,rem-1),solve(l,r-1,rem-2)));

}



int main(){

    for(int i=0;i<105;i++)

        for(int j=0;j<105;j++)

            for(int k=0;k<105;k++)

                dp[i][j][k]=-oo;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++)

        scanf("%d",&a[i]);

    printf("%lld",solve(0,n-1,k));

}






// Faster C++ solution for the same problem (measured speedup: 10.643394079250173x):
//H

#include<cstdio>

#include<iostream>

using namespace std;

long long f[110][55][55];

long long a[55];

int main()

{

	int min=-1000000010;

	long long res=min;

	int n,k;

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)

		scanf("%lld",&a[i]);

	

	for(int i=0;i<=k;i++)

		for(int j=0;j<=n;j++)

			for(int k=0;k<=n;k++)

				f[i][j][k]=min;

	

	f[0][1][n]=0;

	for(int i=1;i<=k;i++)//区间[l,r]含l与r 

	{

		for(int l=1;l<=n;l++)

		{

			for(int r=n;r>=l-1;r--)

			{

				if(i>=2&&l-1>=1&&f[i-2][l-1][r]>f[i][l][r])

					f[i][l][r]=f[i-2][l-1][r];

					

				if(i>=2&&r+1<=n&&f[i-2][l][r+1]>f[i][l][r])

					f[i][l][r]=f[i-2][l][r+1];

					

				if(f[i-1][l-1][r]!=min&&l-1>=1&&f[i-1][l-1][r]+a[l-1]>f[i][l][r])

					f[i][l][r]=f[i-1][l-1][r]+a[l-1];

					

				if(f[i-1][l][r+1]!=min&&r+1<=n&&f[i-1][l][r+1]+a[r+1]>f[i][l][r])

					f[i][l][r]=f[i-1][l][r+1]+a[r+1];

				//f[i-1][l][r+1]!=min 保证不是直接到达此区间，而是从大区间合法到小区间 

				res=max(res,f[i][l][r]);

			}

		}

	}

	if(res>=0)

		cout<<res<<endl;

	else

		cout<<0<<endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define ll long long



const int N = 1e6+3,M=55;



const ll oo=1e18;



int n,m,ans,tc,a[N],b[N],k;



#define f first



#define s second



const int dx[]={0,0,1,-1},

          dy[]={1,-1,0,0};



char s[N];



ll dp[105][105][105];



ll solve(int l,int r,int rem){

    if (rem<0)

        return -1e9;

    if (l>r)

        return 0;

    ll &ret = dp[l][r][rem];

    if (ret!=-oo)

        return ret;

    ret=0;

    ret=max(ret,max(a[l]+solve(l+1,r,rem-1),solve(l+1,r,rem-2)));

    return ret=max(ret,max(a[r]+solve(l,r-1,rem-1),solve(l,r-1,rem-2)));

}



int main(){

    for(int i=0;i<105;i++)

        for(int j=0;j<105;j++)

            for(int k=0;k<105;k++)

                dp[i][j][k]=-oo;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++)

        scanf("%d",&a[i]);

    printf("%lld",solve(0,n-1,k));

}






// Faster C++ solution for the same problem (measured speedup: 10.748499598184535x):
#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 103

int main()

{

    int n, k, r, res = 0;

    int i, j;

    int a[MAXN], plate[MAXN];

    scanf("%d%d",&n, &k);

    for(int i = 0; i < n; i++)

    {

        scanf("%d", a+i);

    }

    r = min(n, k);

    for(int A = 0; A <= r; A++)

    {

        for(int B = 0; B <= r-A; B++)

        {

            for(i = 0; i < A; i++)

            {

                plate[i] = a[i];

            }

            for(j = 0; j < B; j++)

            {

                plate[i+j] = a[n-1-j];

            }

            sort(plate, plate+A+B);

            i = 0;

            while(i < k-A-B && plate[i] < 0) //是k不是r

            {

                i++;

            }

            int sum = 0;

            for(; i < A+B; i++)

            {

                sum += plate[i];

            }

            res = max(res, sum);

        }

    }

    printf("%d\n", res);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



#define ll long long



const int N = 1e6+3,M=55;



const ll oo=1e18;



int n,m,ans,tc,a[N],b[N],k;



#define f first



#define s second



const int dx[]={0,0,1,-1},

          dy[]={1,-1,0,0};



char s[N];



ll dp[105][105][105];



ll solve(int l,int r,int rem){

    if (rem<0)

        return -1e9;

    if (l>r)

        return 0;

    ll &ret = dp[l][r][rem];

    if (ret!=-oo)

        return ret;

    ret=0;

    ret=max(ret,max(a[l]+solve(l+1,r,rem-1),solve(l+1,r,rem-2)));

    return ret=max(ret,max(a[r]+solve(l,r-1,rem-1),solve(l,r-1,rem-2)));

}



int main(){

    for(int i=0;i<105;i++)

        for(int j=0;j<105;j++)

            for(int k=0;k<105;k++)

                dp[i][j][k]=-oo;

    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++)

        scanf("%d",&a[i]);

    printf("%lld",solve(0,n-1,k));

}






// Faster C++ solution for the same problem (measured speedup: 10.794264422676104x):
#include<bits/stdc++.h>

using namespace std;

const int maxn=50+10;

const int INF=-0x3f3f3f3f;

int n,m,k,v[maxn];

long long ans=INF,tmp;

vector<int> g;

void fun(int x,int y,int p){

	int l=1,r=n;

	g.clear();

	tmp=0;

	while(x){

		g.push_back(v[l]);

		l++;

		x--; 

	}

	while(y){

		g.push_back(v[r]);

		r--;

		y--;

	}

	sort(g.begin(),g.end(),greater<int>());

	for(int idx=0;idx<g.size()-p;idx++){

		tmp+=g[idx];

	}

	ans=max(ans,tmp);

}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++){

		scanf("%d",&v[i]);

	}

	m=min(n,k);

	for(int i=0;i<=m;i++){

		for(int j=0;i+j<=m;j++){

			for(int p=0;i+j+p<=k;p++){

				if(i+j<p) break;

				else fun(i,j,p);

			}

		}

	}

	printf("%lld",ans);

}