def search(m, k)
	r = @ratio[k]
	return [m, m] unless r
	n, q = search(m / r, k + 1)
	n1, pay1 = n + m % r, r * q + m % r
	n, q = search(-(-m / r), k + 1)
	n2, pay2 = n + (-m % r), r * q
	n1 < n2 ? [n1, pay1] : [n2, pay2]
end
 
coin = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000]
@ratio = (0..coin.size - 2).map {|i| coin[i + 1] / coin[i]}
 
DATA.each do |d|
	m = d.to_i
	n, pay = search(m, 0)
	puts "M = #{m} -> #{pay}yen, #{n}mai"
end
 
__END__
110
555
9999

ZGVmIHNlYXJjaChtLCBrKQoJciA9IEByYXRpb1trXQoJcmV0dXJuIFttLCBtXSB1bmxlc3MgcgoJbiwgcSA9IHNlYXJjaChtIC8gciwgayArIDEpCgluMSwgcGF5MSA9IG4gKyBtICUgciwgciAqIHEgKyBtICUgcgoJbiwgcSA9IHNlYXJjaCgtKC1tIC8gciksIGsgKyAxKQoJbjIsIHBheTIgPSBuICsgKC1tICUgciksIHIgKiBxCgluMSA8IG4yID8gW24xLCBwYXkxXSA6IFtuMiwgcGF5Ml0KZW5kCgpjb2luID0gWzEsIDUsIDEwLCA1MCwgMTAwLCA1MDAsIDEwMDAsIDUwMDAsIDEwMDAwXQpAcmF0aW8gPSAoMC4uY29pbi5zaXplIC0gMikubWFwIHt8aXwgY29pbltpICsgMV0gLyBjb2luW2ldfQoKREFUQS5lYWNoIGRvIHxkfAoJbSA9IGQudG9faQoJbiwgcGF5ID0gc2VhcmNoKG0sIDApCglwdXRzICJNID0gI3ttfSAtPiAje3BheX15ZW4sICN7bn1tYWkiCmVuZAoKX19FTkRfXwoxMTAKNTU1Cjk5OTk=