#include<bits/stdc++.h>
#define ll long long
using namespace std;
int m,n;
int a[20000];
int ans;
int dp(int l,int r)
{
	int f[2000]={0};
	for(int q=l;q<=r;q++)
	{
		f[q]=max(f[q-1],0);
		f[q]+=a[q];
	}
	int v=0;
	for(int q=l;q<=r;q++)
	{
		v=max(v,f[q]);
	}
	return v;
}
int main(){
	freopen("white_lies.in","r",stdin);
	freopen("white_lies.out","w",stdout);
while(cin>>m)
{
	ans=0;
	int l,r,now=0,zm;
	cin>>n;for(int q=1;q<=n;q++) cin>>a[q];
	if(m==1) ans=dp(1,n);
		if(m==2)
	{
		for(int i=1;i<=n;i++) ans=max(ans,dp(1,i)+dp(i+1,n));	
	}
		
	
	cout<<ans<<endl;
}
return 0;
}