#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcount(s)
#define lb(s) (s&-s)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0' && c<='9')x=x*10 + c-'0',c=getchar();
	return x*f;
}
const int N=2e5+3;
const int mod=998244353;
inline void Ad(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
int n,m,TYP;
ll a[N];
ll f[4][4][N];
ll g[4][4][N];
inline void ckmax(ll &x,ll y){x=x>y?x:y;}
inline void solve(int l,int r){// solve(l,r)  max i is r-l+1 ,so i=1 place l,means(i+l-1);
	if(l==r){
		rep(d,0,3)f[d][d][l] = a[l]*(bit(d,1)-bit(d,0));
		return ;
	}
	int mid=(l+r)>>1;solve(l,mid),solve(mid+1,r);
	rep(d,0,3)rep(p,0,3)rep(i,l,r)g[d][p][i]=-1e18;
	if(mid-l+1>=2 && r-mid>=2){//Mink
		rep(d,0,3)rep(p,0,3)if(((d^p)==3) || (d==3 && p==3))rep(L,0,3)rep(R,0,3){
			vector<ll>vec1,vec2,vec(1,f[L][d][l+1]+f[p][R][mid+2]);//start with  j=3 + (d==3 && p==3)
			rep(i,3,mid-l+1)vec1.pb(f[L][d][i+l-1]-f[L][d][i+l-2]);
			rep(i,3,r-mid)vec2.pb(f[p][R][mid+i]-f[p][R][mid+i-1]);
			for(int i=0,j=0;i<vec1.size() || j<vec2.size();){
				if(i<vec1.size() && (j==vec2.size() || vec1[i]>vec2[j]))vec.pb(vec.back()+vec1[i++]);
				else vec.pb(vec.back()+vec2[j++]);
			}
			rep(j,3+(d==3 && p==3),r-l+1-!(d==3 && p==3))ckmax(g[L][R][j+l-1],vec[j-3-(d==3 && p==3)]);
		}
	}
	rep(d,0,3)rep(p,0,3){
		if((d&p)==0){
			rep(R,0,3)rep(i,2,r-mid) ckmax(g[d|p][R][i+l-1],f[d][d][l]+f[p][R][mid+i]);
			rep(L,0,3)rep(i,2,mid-l+1) ckmax(g[L][d|p][i+l-1],f[L][d][l+i-1]+f[p][p][mid+1]);
		}
		if(p==3){
			rep(R,0,3)rep(i,2,r-mid) ckmax(g[d][R][i+l],f[d][d][l]+f[p][R][mid+i]);
		}
		if(d==3){
			rep(L,0,3)rep(i,2,mid-l+1) ckmax(g[L][p][i+l],f[L][d][l+i-1]+f[p][p][mid+1]);
		}
	}
	rep(d,0,3)rep(p,0,3){
		if((d&p)==0)ckmax(g[(d|p)][(d|p)][l],f[d][d][l]+f[p][p][mid+1]);
		ckmax(g[d][p][l+1],f[d][d][l]+f[p][p][mid+1]);
	}
	rep(L,0,3)rep(R,0,3)rep(i,l,r)f[L][R][i]=g[L][R][i];
}
int main(){
	//freopen("data.in","r",stdin);
	//freopen("tower.in","r",stdin);
	//freopen("tower.out","w",stdout);
	n=read(),m=read(),TYP=read();rep(i,1,n)a[i]=read();
	solve(1,n);
	if(TYP==1)printf("%lld",f[3][3][m]);
	else rep(i,1,m)printf("%lld\n",f[3][3][i]);
	return 0;
}