import Data.IntMap ((!))
import qualified Data.IntMap as M
import Control.Monad
import Data.Bits

main = do
 n <- readLn
 ms <- map read . words <$> getContents
 print (mds n ms)

mds n ms = snd $ M.findMax $ foldr (dp n ms) (M.singleton 0 0) (replicate n [0..n-1])

dp n ms ds im = M.unionsWith min $ (im:) $ map buy ds
 where
  buy d = M.mapKeys (flip setBit d) $ M.mapWithKey (\k v -> v + (max 0 ((ms!!d) - (table!k)))) $
          M.filterWithKey (\k _ -> not (testBit k d)) im      
  table = M.fromDistinctAscList $ do
   bs <- replicateM n [0,1]
   let k = sum (zipWith (*) (reverse bs) (map bit [0..n]))
   let v = sum (zipWith (*) (reverse bs) ms) `mod` 1000
   return (k,v)