import Data.List
main = getLine >>= main' . read . last . words
    where
        main' t = getLine >>= print . solve (t `div` 2) . map read . words

solve :: Int -> [Int] -> Int
solve t = {-min t .-} snd . foldl' ff (0, 0) . snd . build
    where
        ff (v, n) x
            | v < x = (x, 1)
            | v == x = (v, n + 1)
            | otherwise = (v, n)

        build (z : zs)
            | z > x = (z, 0 : zs')
            | otherwise = (x, (x - z) : zs')
            where
                (x, zs') = build zs

        build _ = (0, [])
