{-# LANGUAGE RankNTypes #-}
    
import Control.Monad.State
import Control.Monad.ST
import Data.Array.ST
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V

main :: IO ()
main = readContents 2 >>= print . solve

solve :: [[Int]] -> Int
solve [[n, k], vs] = runST (initialize >>= stAction)
    where
        ws = V.fromList vs

        initialize :: ST s (Table s (Int, Int, Int) Int)
        initialize = newArray ((0, 0, 0), (n, n, k + 1)) Nothing
        
        stAction t 
            | n == 1 = return (max 0 $ head vs)
            | otherwise = evalMemo calc (0, n - 1, k) t 

        calc f (a, b, c)
            | c == 0 || a > b = return 0
            | av >= 0 && bv >= 0 = maximum <$> sequence [(+ av) <$> f (a + 1, b, c - 1), (+ bv) <$> f (a, b - 1, c - 1)]
            | av >= 0 && c > 1 = maximum <$> sequence [(+ av) <$> f (a + 1, b, c - 1), f (a, b - 1, c - 2)]
            | av >= 0 = (+ av) <$> f (a + 1, b, c - 1)
            | bv >= 0 && c > 1 = maximum <$> sequence [(+ bv) <$> f (a, b - 1, c - 1), f (a + 1, b, c - 2)]
            | bv >= 0 = (+ bv) <$> f (a, b - 1, c - 1)
            | c > 1 = maximum <$> sequence [f (a + 1, b, c - 2), f (a, b - 1, c - 2)]
            | otherwise = return 0
            where
                av = ws V.! a
                bv = ws V.! b

readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

type Table s a b = STArray s a (Maybe b)
type Memo s a b = a -> StateT (Table s a b) (ST s) b

evalMemo :: (Ix a) => (forall s. Memo s a b -> Memo s a b) -> a -> Table s a b -> ST s b
evalMemo f k = evalStateT (memoizeFix f k)

runMemo :: (Ix a) => (forall s. Memo s a b -> Memo s a b) -> a -> Table s a b -> ST s (b, Table s a b)
runMemo f k = runStateT (memoizeFix f k)

memoizeFix :: (Ix a) => (forall s. Memo s a b -> Memo s a b) -> forall s. Memo s a b
memoizeFix f k = get >>= (\arr -> lift (readArray arr k) >>= maybe (f (memoizeFix f) k >>= ((<$) <*> (lift . writeArray arr k . Just))) return)