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
 

aW1wb3J0IENvbnRyb2wuTW9uYWQKaW1wb3J0IERhdGEuQXJyYXkKaW1wb3J0IENvbnRyb2wuRXhjZXB0aW9uIChoYW5kbGUsIFNvbWVFeGNlcHRpb24pCgptYWluIDo6IElPICgpCm1haW4gPSBoYW5kbGUgZXJyb3JIYW5kbGVyICQgKHByaW50IC4gbWluVHVybnMpID08PCBmbWFwIHJlYWQgZ2V0TGluZQoKZXJyb3JIYW5kbGVyIDo6IFNvbWVFeGNlcHRpb24gLT4gSU8gKCkKZXJyb3JIYW5kbGVyIF8gPSBwdXRTdHJMbiAiLTEiCgptaW5UdXJucyA6OiAoSW50LCBJbnQpIC0+IEludAptaW5UdXJucyB4CiAgfCB4IDw9ICgxLCAxKSA9IC0xCiAgfCBvdGhlcndpc2UgPSBtYXliZSAwIGxlbmd0aCBscyAtIDEKICAgICAgd2hlcmUgbHMgPSBzZWFyY2ggKGdlbkJvYXJkcyBUcnVlKSBnb2FsIG51bSBbaW5pdGlhbEJvYXJkXQogICAgICAgICAgICAgICAgIGBtcGx1c2AKICAgICAgICAgICAgICAgICBzZWFyY2ggKGdlbkJvYXJkcyBGYWxzZSkgZ29hbCBudW0gW2luaXRpYWxCb2FyZF0KICAgICAgICAgICAgaW5pdGlhbEJvYXJkID0gQm9hcmQgKDEsIDEpIChsaXN0QXJyYXkgKCgxLCAxKSwgeCkgJCByZXBlYXQgKFRpbGUgRmFsc2UgMCkpCiAgICAgICAgICAgIG51bSA9IHVuY3VycnkgKCopIHgKCmRhdGEgVGlsZSA9IFRpbGUge3BhaW50ZWQgOjogQm9vbCwgd2V0IDo6IEludH0gZGVyaXZpbmcgKEVxLCBTaG93KQpkYXRhIEJvYXJkID0gQm9hcmQge3BvcyA6OiAoSW50LCBJbnQpLCB0aWxlcyA6OiBBcnJheSAoSW50LCBJbnQpIFRpbGV9IGRlcml2aW5nIChFcSwgU2hvdykKdHlwZSBCb2FyZHMgPSBbQm9hcmRdCgpnb2FsIDo6IEJvYXJkcyAtPiBCb29sCmdvYWwgW10gICAgICAgICAgICAgICAgPSBGYWxzZQpnb2FsICgoQm9hcmQgXyB0cyk6XykgID0gYWxsIHBhaW50ZWQgJCBlbGVtcyB0cwoKZ2VuQm9hcmRzIDo6IEJvb2wgLT4gQm9hcmRzIC0+IFtCb2FyZHNdCmdlbkJvYXJkcyBfIFtdID0gW10KZ2VuQm9hcmRzIGlwYXNzIG5AKGI6YnMpID0gZ2VuQm9hcmRzJyBiCiAgd2hlcmUKICAgIGdlbkJvYXJkcycgKEJvYXJkIHAgdHMpID0gbWFwICg6IG4pICQgYWxsUGFpbnRzICsrIGFsbFN0ZXBzICsrIHBhc3MKICAgICAgd2hlcmUKICAgICAgICBhbGxQYWludHMgPQogICAgICAgICAgW0JvYXJkIHAgKHRzJyAvLyBbKGksIHQge3BhaW50ZWQgPSBUcnVlLCB3ZXQgPSA1fSldKQogICAgICAgICAgICB8IChpLCB0KSA8LSBhc3NvY3MgdHMsIG1hbmRpc3QgcCBpID09IDEsIG5vdCAocGFpbnRlZCB0KV0KICAgICAgICBhbGxTdGVwcyA9CiAgICAgICAgICBbQm9hcmQgaSB0cycKICAgICAgICAgICAgfCAoaSwgdCkgPC0gYXNzb2NzIHRzLCBtYW5kaXN0IHAgaSA9PSAxLCB3ZXQgdCA9PSAwLCBpIGBub3RFbGVtcmAgbWFwIHBvcyBic10KICAgICAgICBwYXNzID0gaWYgaXBhc3MgdGhlbiBbXSBlbHNlIFtCb2FyZCBwIHRzJ10KICAgICAgICB0cycgPSBmbWFwIGRyeSB0cwogICAgICAgIGRyeSB0IHwgdyA8LSB3ZXQgdCwgdyA+IDAgPSB0IHt3ZXQgPSB3IC0gMX0KICAgICAgICAgICAgICB8IG90aGVyd2lzZSAgICAgICAgID0gdAogICAgICAgIG5vdEVsZW1yIDo6IEVxIGEgPT4gYSAtPiBbYV0gLT4gQm9vbAogICAgICAgIG5vdEVsZW1yIHEgPSBmb2xkciAoKCYmKSAuICgvPXEpKSBUcnVlCgptYW5kaXN0IDo6IChJbnQsIEludCkgLT4gKEludCwgSW50KSAtPiBJbnQKbWFuZGlzdCAoeDEsIHkxKSAoeDIsIHkyKSA9IGFicyAoeDEgLSB4MikgKyBhYnMgKHkxIC0geTIpCgpzZWFyY2ggOjogKEVxIGEsIE1vbmFkUGx1cyBtKSA9PiAoYSAtPiBbYV0pIC0+IChhIC0+IEJvb2wpIC0+IEludCAtPiBhIC0+IG0gYQpzZWFyY2ggZiBnIGwgeCA9IG1zdW0gJCBtYXAgKHNlYXJjaCcgW3hdKSAoW2wgKyAzIC4uIGwgKiA1XSA6OiBbSW50XSkKICB3aGVyZQogICAgc2VhcmNoJyAoeTp5cykgZAogICAgICB8IGQgPT0gMCAgICA9IG16ZXJvCiAgICAgIHwgZyB5ICAgICAgID0gcmV0dXJuIHkgYG1wbHVzYCBzZWFyY2gnIHlzIGQKICAgICAgfCBvdGhlcndpc2UgPSBzZWFyY2gnIChmIHkpIChkIC0gMSkgYG1wbHVzYCBzZWFyY2gnIHlzIGQKICAgIHNlYXJjaCcgXyBfICAgPSBtemVybwo=

KDMsMyk=

(3,3)