import Data.List (notElem, nub, minimumBy, group)
import Control.Monad (filterM, guard)
pay 0 = []
pay n | n >= 500 = 500:pay (n - 500)
| n >= 100 = 100:pay (n - 100)
| n >= 50 = 50 :pay (n - 50)
| n >= 10 = 10 :pay (n - 10)
| n >= 5 = 5 :pay (n - 5)
| otherwise = 1 :pay (n - 1)
powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])
g :: Int -> [(Int,Int)] -> [[Int]]
g n xs = do
p <- powerset $ concatMap (\(x,y) -> replicate y x) xs
guard $ (total p) >= n
guard $ and $ map (\x -> x `notElem` pay (total p - n)) p
return p
where total p = sum p
f n xs = map (\xs -> (head xs, length xs)) $ group $ minimumBy (\x y -> ret x `compare` ret y) $ nub $ g n xs
where num = sum $ map snd xs
ret p = num - (length p) + length (pay ((sum p) - n))
