import Data.Array((!), listArray)
main = interact $ show.helper.(map read).words
helper::[Integer]->Integer
helper (x:xs) = fonk x a 
            where a = listArray ((1, 1), (x, 3)) xs
                  fonk::Integer->listArray (Integer, Integer) Integer->Integer
                  fonk x a = maximum [dp!(1, aa)|aa<-[1..3]]
                  f::(Integer, Integer)->Integer
                  f (i, j) 
                       | i == x = maximum [a!(i, aa)|aa<-[1..3], aa /= j]
                       | otherwise =a!(i, j) +  
                                    maximum [dp!(i+1, aa)|aa<-[1..3], aa /= j]
                  --dp::listArray (Integer, Integer) Integer
                  dp = listArray ((1, 1), (x, 3)) $ 
                       map f [(ii, jj)| ii<-[1..x], jj<-[1..3]]

{-
dp = listArray ((1, 1), (1, 3)) $ map (+) [(ii, jj)| ii<-[1..1], jj<-[1..3]]

-}
