DouKaku?

import scala.collection.mutable.HashMap
import scala.collection.Map.Projection
def pay(money:Int, wallet:Map[Int, Int]):Projection[Int,Int] = {
  var m = money
  val r = new HashMap[Int,Int]
  m = wallet.keys./:(0){(r,k) => r+k*wallet(k)} - m
  if(m<0) throw new RuntimeException("Money!")
  List(500, 100, 50, 10, 5, 1).foreach(c => {
    r(c) = wallet.getOrElse(c, 0) - m/c
    m = m%c
  })
  r.filterKeys(k => r(k)>0)
}
pay(147, Map(1 -> 2, 5 -> 300, 10 -> 4, 100 -> 3)).foreach(p => print(p._1+":"+p._2+","))