동전

면접 대비

시간 제한2초메모리 제한128 MB

요약

1, 5, 10, 25센트 동전의 개수가 제한된 상황에서 정확히 X센트를 만들면서 사용하는 동전 총수를 최대화하는 조합을 구합니다.

문제

찰리는 1센트, 5센트(니켈), 10센트(다임), 25센트(쿼터) 동전을 가지고 있다. 각각의 개수는 A, B, C, D개이다.

찰리는 X센트짜리 커피 값을 정확히 지불하려고 한다. 가지고 있는 동전 수의 한도를 넘지 않으면서, 사용하는 동전의 총 개수가 최대가 되도록 해야 한다.

이때 사용할 1센트, 니켈, 다임, 쿼터의 개수를 구하라.

첫째 줄에 다섯 정수 X, A, B, C, D가 공백으로 구분되어 주어진다.

정확히 X센트를 만들 수 있다면, 사용할 1센트, 니켈, 다임, 쿼터의 개수를 차례로 출력한다. 이때 사용한 동전의 총 개수가 최대여야 한다.

불가능하면 0 0 0 0을 출력한다.