문제
철수는 동전 자판기를 자주 이용한다.
그래서 그는 항상 상당히 많은 개수의 동전들을 주머니에 가지고 다니는데, 동전들이 주머니에서 짤랑거리는 것을 듣기 싫어한다.
그래서 철수는 동전자판기에서 무언가 살 때는 되도록 많은 개수의 동전을 사용한다.
철수의 주위에 있는 자판기들은 아주 구형인 모델이어서 지폐를 사용할 수 없고, 또, 정확한 액수만을 넣어야 한다.
이 문제는 철수가 가지고 있는 동전 중 최대 개수의 동전을 이용하여 자판기의 물건을 구입하는 방법을 출력하는 프로그램을 작성하는 것이다.
입력
첫줄에는 자판기에서 구입하려는 물건의 값 W가 주어진다.
둘째줄에는 6개의 정수가 주어진다.
각각의 정수는 철수가 가지고 있는 500원짜리, 100원짜리, 50원짜리, 10원짜리, 5원짜리, 1원짜리 동전들의 개수를 순서대로 나타낸다.
각각의 동전 개수는 1 이상 50 이하이다. 정수들 사이에는 빈칸이 하나 있다.
출력
첫 줄에는 물건의 구입에 사용될 수 있는 최대 개수의 동전수를 출력한다.
둘째줄에는 최대 개수를 구성하는 동전들에 대해 500원짜리부터 시작하여 각각의 개수를 순서대로 출력한다.
즉, 6개의 정수가 출력되어야 하며 사용하지 않는 액수의 동전이 있으면 그 액수에 대해서는0을 출력한다.
※ 어떠한 동전들의 조합으로도 정확한 물건값이 될 수 없는 경우는 입력으로 주어지지 않는다.
예제1
입력
13
452634
출력
5
000023
태그
출처
제5회 전남대학교 경시대회