import Data.Ord
import Data.List

main = interact $ init . unlines . map (show' . make_purse_light) . read' . lines
 where
  read' ("0":_) = []
  read' (m:coins:xs) = (read m, (map read . words) coins) : read' xs
  show' = unlines . filter ((/='0') . last) . zipWith (++) ["10 ","50 ","100 ","500 "] . map show

make_purse_light (m,[n10,n50,n100,n500]) = minimumBy (comparing sum) [change 0, change 50, change 100]
 where change n = head $ [[n10',n50',n100',n500']| n500'<-[0..n500], n100'<-[0..n100], n50'<-[0..n50], n10'<-[0..n10],
                                                   sum [n10'*10,n50'*50,n100'*100,n500'*500] == m+n] ++ [[maxBound::Int]]