####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
eval"N,K,*V="+`dd`.split*?,;
p (0..L=[K,N].min).map{|a|(0..L-a).map{|b|
s=V[0,a]+V[-b,b];
(s+s.min(K-a-b).map{|x|x<0?-x:0}).reduce 0,:+
}.max}.max
