import Data.List
import Control.Monad
 
numOfSplits :: Integer -> Integer
numOfSplits a
  | (abs a) > 500 = -1
  | (abs a) == 0 = 0
  | otherwise = intzahler $  makeChange [200,100,50,20,10,5,2,1] (abs a) 200
 
intzahler :: [[Integer]] -> Integer
intzahler array
  | array == [] = 0
  | otherwise = 1 + intzahler (tail array)
 
makeChange :: [Integer] -> Integer -> Integer -> [[Integer]]
makeChange coins amount maxCoins
  | amount < 0  = []
  | amount == 0 = [[]]
  | null coins  = []
  | amount `div` maximum coins > maxCoins = [] -- optimisation
  | amount > 0  =
    do x <- coins
       xs <- makeChange (filter (<= x) coins) (amount - x) (maxCoins - 1)
       guard $ genericLength (x:xs) <= maxCoins
       return (x:xs)
 
main = do
  let n = 180
  putStrLn $ "numOfSplits " ++ show n ++ " = " ++ show (numOfSplits n)
 

aW1wb3J0IERhdGEuTGlzdAppbXBvcnQgQ29udHJvbC5Nb25hZAoKbnVtT2ZTcGxpdHMgOjogSW50ZWdlciAtPiBJbnRlZ2VyCm51bU9mU3BsaXRzIGEKICB8IChhYnMgYSkgPiA1MDAgPSAtMQogIHwgKGFicyBhKSA9PSAwID0gMAogIHwgb3RoZXJ3aXNlID0gaW50emFobGVyICQgIG1ha2VDaGFuZ2UgWzIwMCwxMDAsNTAsMjAsMTAsNSwyLDFdIChhYnMgYSkgMjAwCgppbnR6YWhsZXIgOjogW1tJbnRlZ2VyXV0gLT4gSW50ZWdlcgppbnR6YWhsZXIgYXJyYXkKICB8IGFycmF5ID09IFtdID0gMAogIHwgb3RoZXJ3aXNlID0gMSArIGludHphaGxlciAodGFpbCBhcnJheSkKCm1ha2VDaGFuZ2UgOjogW0ludGVnZXJdIC0+IEludGVnZXIgLT4gSW50ZWdlciAtPiBbW0ludGVnZXJdXQptYWtlQ2hhbmdlIGNvaW5zIGFtb3VudCBtYXhDb2lucwogIHwgYW1vdW50IDwgMCAgPSBbXQogIHwgYW1vdW50ID09IDAgPSBbW11dCiAgfCBudWxsIGNvaW5zICA9IFtdCiAgfCBhbW91bnQgYGRpdmAgbWF4aW11bSBjb2lucyA+IG1heENvaW5zID0gW10gLS0gb3B0aW1pc2F0aW9uCiAgfCBhbW91bnQgPiAwICA9CiAgICBkbyB4IDwtIGNvaW5zCiAgICAgICB4cyA8LSBtYWtlQ2hhbmdlIChmaWx0ZXIgKDw9IHgpIGNvaW5zKSAoYW1vdW50IC0geCkgKG1heENvaW5zIC0gMSkKICAgICAgIGd1YXJkICQgZ2VuZXJpY0xlbmd0aCAoeDp4cykgPD0gbWF4Q29pbnMKICAgICAgIHJldHVybiAoeDp4cykKCm1haW4gPSBkbwogIGxldCBuID0gMTgwCiAgcHV0U3RyTG4gJCAibnVtT2ZTcGxpdHMgIiArKyBzaG93IG4gKysgIiA9ICIgKysgc2hvdyAobnVtT2ZTcGxpdHMgbikK