# ICPC2005 ProblemB

Make Purse Light!

```(defun calc-return (money)
(multiple-value-bind (500-yen rem) (floor money 500)
(multiple-value-bind (100-yen rem) (floor rem 100)
(multiple-value-bind (50-yen rem) (floor rem 50)
(multiple-value-bind (10-yen rem) (floor rem 10)
`(,10-yen ,50-yen ,100-yen ,500-yen))))))

(defun calc-money (list)
(let
((10-yen (car list))
(+ (* 500-yen 500) (* 100-yen 100) (* 50-yen 50) (* 10-yen 10))))

(defun calc-bill-pattern (bill money-list)
(loop for 10-yen from 0 upto (car money-list)
append
(loop for 50-yen from 0 upto (cadr money-list)
append
(loop for 100-yen from 0 upto (caddr money-list)
append
(loop for 500-yen from 0 upto (cadddr money-list)
when (>= (calc-money `(,10-yen ,50-yen ,100-yen ,500-yen)) bill)
collect `(,10-yen ,50-yen ,100-yen ,500-yen))))))

(defun calc-rem-money (walet pay)
(mapcar #'- walet pay))

(defun collect-patternp (pay res)
(every (lambda (x y) (if (not (zerop x)) (zerop y) t)) pay res))

(defun print-money (money-list)
(loop
for money in money-list
for i in '(10 50 100 500)
when (not (zerop money))
do
(format t "~A ~A~%" i money)))

(defun calc-res (pay walet)
(caar
(sort
(loop
for pay-pattern in (calc-bill-pattern pay walet)
for rem-in-walet = (calc-rem-money walet pay-pattern)
for return-money = (calc-return (- (calc-money pay-pattern) pay))
for res-in-walet = (mapcar #'+ rem-in-walet return-money)
when (collect-patternp pay-pattern return-money)
collect `(,pay-pattern ,res-in-walet))
#'< :key (lambda (x) (apply #'+ (cadr x))))))

(defun main ()
(loop