import Data.Array
import Data.List
import Data.List.Split


type Width = Int
type Height = Int
type Enemy = (Int,Int)
type Player = (Int,Int)
type Cost = Int
type Situation = (Width, Height, Player, [Enemy], Cost)

main = do
  input <- getSplitedLines
  let (w:h:_) = head input
  let enemys = map (\(a:b:_) -> (a, b)) $ drop 1 input
  let player = (0,0)
  let cost = 0
  let minimumCost = calcMinimumCost (w, h, player, enemys, cost)
  putStrLn $ show minimumCost

calcMinimumCost :: Situation -> Cost
calcMinimumCost situation = calcMinimumCost' [explosion situation]
  where
    calcMinimumCost' :: [Situation] -> Cost
    calcMinimumCost' situations = case getEnd situations of
      Nothing -> calcMinimumCost' nextSituations
      Just (_, _, _, _, c)  -> c
      where
        nextSituations = situations >>= getNextSituation

getNextSituation :: Situation -> [Situation]
getNextSituation situation = map explosion $ getNextMove situation

getNextMove :: Situation -> [Situation]
getNextMove (w, h, (px,py), es, c)
  | px < w-1 && py < h-1 = [(w, h, (px + 1,py), es, nextCost), (w, h, (px,py + 1), es, nextCost)]
  | px < w-1             = [(w, h, (px + 1,py), es, nextCost)]
  | py < h-1             = [(w, h, (px,py + 1), es, nextCost)]
  | otherwise			 = []
  where 
    nextCost = c + 1

explosion :: Situation -> Situation
explosion (w, h, (px,py), es, c) = (w, h, (px,py), filter (not.isHit) es, c)
  where
    isHit (ex,ey) = px == ex || py == ey

getEnd :: [Situation] -> Maybe Situation
getEnd [] = Nothing
getEnd ss = safeHead $ filter isEnd ss

isEnd :: Situation -> Bool
isEnd (_, _, _, [], _) = True
isEnd (_, _, _, _, _) = False
    
safeHead [] = Nothing
safeHead (a:_) = Just a

getSplitedLines =  do
  s <- getContents
  return $ map (map read) $ map (splitOn " ") $ lines s

