{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

import Data.Int

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = do
	[ n, k ] <- readInts
	vs <- readInts
	print $ solve k $ map fromIntegral vs

solve k vs' = runST $ do
	let
		n = length vs'
	vs <- newListArray ( 0, n - 1 ) vs' :: ST s ( STUArray s Int Int64 )
	dp <- newArray ( ( 0, -1, -1 ), ( k, n, n ) ) ( minBound `div` 2 :: Int64 ) :: ST s ( STUArray s ( Int, Int, Int ) Int64 )
	writeArray dp ( 0, 0, n - 1 ) 0
	forM_ [ 0 .. k - 1 ] $ \i -> do
		forM_ [ 0 .. n - 1 ] $ \j1 -> do
			forM_ [ j1 .. n - 1 ] $ \j2 -> do
				modifyArray dp ( i + 1, j1, j2 ) =<< max <$> readArray dp ( i, j1, j2 )
				when ( j1 <= j2 ) $ do
					when ( i + 1 <= k ) $ do
						modifyArray dp ( i + 1, j1 + 1, j2 ) =<< max <$> ( (+)
							<$> readArray vs j1
							<*> readArray dp ( i, j1, j2 ) )
						modifyArray dp ( i + 1, j1, j2 - 1 ) =<< max <$> ( (+)
							<$> readArray vs j2
							<*> readArray dp ( i, j1, j2 ) )
					when ( i + 2 <= k ) $ do
						modifyArray dp ( i + 2, j1 + 1, j2 ) =<< max
							<$> readArray dp ( i, j1, j2 )
						modifyArray dp ( i + 2, j1, j2 - 1 ) =<< max
							<$> readArray dp ( i, j1, j2 )
	res <- newSTRef 0
	forM_ [ 0 .. n - 1 ] $ \j1 -> do
		forM_ [ 0 .. n - 1 ] $ \j2 -> do
			modifySTRef res =<< max <$> readArray dp ( k, j1, j2 )
	readSTRef res