C++ :

/*description
*/
/*analysis
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#define limit 200009
using namespace std;
const int inf=0x3f3f3f3f;

struct node
{
	int w,pre,nxt;
	node(int x,int y,int z):w(x),pre(y),nxt(z){}
	node(){}
	bool operator < (const node& a) const
	{ return w<a.w;}
} x;

int n,m,ans=-inf;
int a[limit],cpy[limit],le[limit],ri[limit],t[limit];
bool fg[limit];
void init();
void work(int st,int en);
priority_queue<node> q;

int main()
{
	init();
	return 0;
}

void init()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;++i)scanf("%d",&a[i]);
		if(m>(n>>1))
		{
			printf("Error!\n");
			return ;
		}
		work(1,n-1);//不要1 
		work(2,n);//不要n 
		printf("%d\n",ans);	
	}
	
}

void work(int st,int en)
{
	int tot=0,pos,L,R;
	memset(cpy,0x80,sizeof(cpy));
	for(int i=st;i<=en;++i)cpy[i]=a[i];
	while(!q.empty())q.pop();
	
	for(int i=st;i<=en;++i)
	{
		q.push(node(cpy[i],i,1));
		le[i]=i-1;ri[i]=i+1;t[i]=1;
	}
	memset(fg,0,sizeof(fg));
	
	for(int i=1;i<=m;++i)
	{
		for(x=q.top();fg[x.pre]||x.nxt!=t[x.pre];q.pop(),x=q.top());
		x=q.top();//找到一个可用解 
		tot+=x.w;
		//printf("%d ",x.w);
		pos=x.pre;
		L=le[pos],R=ri[pos];//左右位置 
		ri[L]=ri[R];//去掉左边 
		le[ri[R]]=L;
		fg[pos]=fg[R]=1;//标记不可使用 
		cpy[L]=cpy[L]+cpy[R]-cpy[pos];
		q.push(node(cpy[L],L,++t[L]));
	}
	if(tot>ans)ans=tot;
	//printf("\n");
}