잔돈

잭 세이거트는 5센트, 10센트, 20센트, 50센트짜리 동전으로 주머니를 가득 채우고 다닌다. 값을 치를 때는 언제나 동전을 가장 적게 쓰는 방법을 고른다. 동전을 잔뜩 들고 다니는 것이 자기 인생의 사명이라고 믿기 때문에, 한 번에 내놓는 동전 개수를 최소로 줄이려 한다.

왜 이렇게 되었는지는 아무도 모른다. 태어나던 날 어머니의 산부인과 의사가 그를 머리부터 떨어뜨렸다는 이야기만 전해질 뿐이다.

주머니에 있는 5센트, 10센트, 20센트, 50센트 동전의 개수와 내야 할 금액이 주어진다. 각 동전을 몇 개씩 내야 하는지와 사용한 동전의 총개수를 구하는 프로그램을 작성하시오. 총개수는 최소여야 한다.

거스름돈은 받지 않으므로 금액을 정확히 맞춰 내야 한다. 값이 $2.35인데 주머니의 동전으로 235센트를 정확히 만들 수 없으면 잭은 이 금액을 낼 수 없다.

첫째 줄에 정수 다섯 개가 공백으로 구분되어 주어진다. 앞의 네 수는 차례대로 잭이 가진 5센트, 10센트, 20센트, 50센트 동전의 개수이고, 다섯째 수는 잭이 내야 할 금액이다. 금액의 단위는 센트이다. 각 동전의 개수는 1,000,000보다 작고, 금액은 0 이상 100,000,000 미만의 정수이다.

잭이 내놓는 5센트, 10센트, 20센트, 50센트 동전의 개수와 사용한 동전의 총개수를 공백으로 구분해 한 줄에 출력한다. 총개수는 최소여야 한다.

동전을 최소로 쓰는 방법이 둘 이상이면 5센트 동전을 가장 적게 쓰는 방법을 출력한다. 그래도 여러 가지가 남으면 10센트 동전을 가장 적게 쓰는 방법을, 그다음에는 20센트 동전을 가장 적게 쓰는 방법을 고른다.

주머니의 동전으로 금액을 정확히 만들 수 없으면 -1만 출력한다.