import Data.Array
import Data.List

main = getLine >>= main' . fmap read . words
    where
        main' [n, k] = getLine >>= print . solve n k . sort . fmap read . words

solve ::  Int -> Int -> [Int] -> Int
solve n k as = count $ splitAt (n `div` 2) xs
    where
        xs = zip [1..] as

        count (ys, z : zs)
            | check z = count $ splitAt (length ys `div` 2) ys
            | otherwise = length ys + 1 + count (splitAt (length zs `div` 2) zs)
        count ([], _) = 0
        count (ys, _) = count $ splitAt (length ys `div` 2) ys

        check (xn, a) = any (\i -> ary ! (i, n)) [(k - a)..(k - 1)]
            where
                ary = array ((0, 0), (k - 1, n)) $
                        ((0, 0), True) : [((i, 0), False) | i <- [1..(k - 1)]] `mappend`
                        [((0, j), True) | j <- [1..n]] `mappend`
                        [((i, j), calc i j na) | i <- [1..(k - 1)], (j, na) <- xs]
                calc i j na
                    | j == xn || i < na = ary ! (i, j - 1)
                    | otherwise = ary ! (i, j - 1) || ary ! (i - na, j - 1)
