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 :: Int -> [Int] -> Int mds n ms = snd $ M.findMax $ foldr (dp n ms t) (M.singleton 0 0) (replicate n [0..n-1]) where t = M.fromDistinctAscList $ do let es = map bit [0..n] bs <- replicateM n [0,1] let k = sum (zipWith (*) (reverse bs) es) let v = sum (zipWith (*) (reverse bs) ms) `mod` 1000 return (k,v) dp n ms t ds im = M.unionsWith min $ map buy ds where buy d = M.mapKeysMonotonic (flip setBit d) $ M.mapWithKey (\k v -> v + (max 0 ((ms!!d) - (t!k)))) $ M.filterWithKey (\k _ -> not (testBit k d)) im