import Control.Monad
import Data.Array
import Control.Exception (handle, SomeException)

main :: IO ()
main = handle errorHandler $ (print . minTurns) =<< fmap read getLine

errorHandler :: SomeException -> IO ()
errorHandler _ = putStrLn "-1"

minTurns :: (Int, Int) -> Int
minTurns x
  | x <= (1, 1) = -1
  | otherwise = maybe 0 length ls - 1
      where ls = search (genBoards True) goal num [initialBoard]
                 `mplus`
                 search (genBoards False) goal num [initialBoard]
            initialBoard = Board (1, 1) (listArray ((1, 1), x) $ repeat (Tile False 0))
            num = uncurry (*) x

data Tile = Tile {painted :: Bool, wet :: Int} deriving (Eq, Show)
data Board = Board {pos :: (Int, Int), tiles :: Array (Int, Int) Tile} deriving (Eq, Show)
type Boards = [Board]

goal :: Boards -> Bool
goal []                = False
goal ((Board _ ts):_)  = all painted $ elems ts

genBoards :: Bool -> Boards -> [Boards]
genBoards _ [] = []
genBoards ipass n@(b:bs) = genBoards' b
  where
    genBoards' (Board p ts) = map (: n) $ allPaints ++ allSteps ++ pass
      where
        allPaints =
          [Board p (ts' // [(i, t {painted = True, wet = 5})])
            | (i, t) <- assocs ts, mandist p i == 1, not (painted t)]
        allSteps =
          [Board i ts'
            | (i, t) <- assocs ts, mandist p i == 1, wet t == 0, i `notElemr` map pos bs]
        pass = if ipass then [] else [Board p ts']
        ts' = fmap dry ts
        dry t | w <- wet t, w > 0 = t {wet = w - 1}
              | otherwise         = t
        notElemr :: Eq a => a -> [a] -> Bool
        notElemr q = foldr ((&&) . (/=q)) True

mandist :: (Int, Int) -> (Int, Int) -> Int
mandist (x1, y1) (x2, y2) = abs (x1 - x2) + abs (y1 - y2)

search :: (Eq a, MonadPlus m) => (a -> [a]) -> (a -> Bool) -> Int -> a -> m a
search f g l x = msum $ map (search' [x]) ([l + 3 .. l * 5] :: [Int])
  where
    search' (y:ys) d
      | d == 0    = mzero
      | g y       = return y `mplus` search' ys d
      | otherwise = search' (f y) (d - 1) `mplus` search' ys d
    search' _ _   = mzero