import Control.Monad
import Data.Array.IO
import Data.Maybe

main = do
    [n,m] <- fmap (map read.words) getLine
    cs <- fmap (map read.words) getLine
    print =<< minCoinsI n cs

minCoinsI :: Int -> [Int] -> IO Int
minCoinsI j coins = do
    minarr <- newListArray (0,j) (repeat 0) :: IO (IOArray Int Int)
    forM_ coins $ \x -> do
        forM_ [0..j] $ \y -> do
            updateArray x y minarr
    return =<< readArray minarr j

updateArray :: Int -> Int -> IOArray Int Int -> IO ()
updateArray i j minarr
  | i == 1 = writeArray minarr j j >> print (i,j) >> getElems minarr >>= print
  | j == 0 = writeArray minarr j 0 >> print (i,j) >> getElems minarr >>= print
  | otherwise = do
      left <- readArray minarr j
      right <- maybeReadArray minarr (j-i)
      let new = min left $ (fromMaybe (maxBound -1)right) + 1
      writeArray minarr j new

maybeReadArray arr ix = do
  (l,r) <- getBounds arr
  if (not (ix `elem` [l..r])) then return Nothing
                              else do
                                e <- readArray arr ix
                                return $ Just e