import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;


abstract class ImmutableLongList implements Iterable<Long> {

    public abstract boolean isEmpty();

    public abstract ImmutableLongList getTail();

    public abstract long getHead();
    private static final ImmutableLongList empty = new ImmutableLongList() {
        @Override
        public boolean isEmpty() {
            return true;
        }

        @Override
        public ImmutableLongList getTail() {
            throw new UnsupportedOperationException("Not supported on empty list.");
        }

        @Override
        public long getHead() {
            throw new UnsupportedOperationException("Not supported on empty list.");
        }
    };
    
    private class ImmutableLongListIterator implements Iterator<Long> {
        private ImmutableLongList currentList;

        public ImmutableLongListIterator(ImmutableLongList currentList) {
            this.currentList = currentList;
        }

        @Override
        public boolean hasNext() {
            return !currentList.isEmpty();
        }

        @Override
        public Long next() {
            final Long result = currentList.getHead();
            currentList = currentList.getTail();
            return result;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
    }

    @Override
    public Iterator<Long> iterator() {
        return new ImmutableLongListIterator(this);
    }

    public static ImmutableLongList getEmpty() {
        return empty;
    }

    private static final class NonEmptyList extends ImmutableLongList {

        private final long head;
        private final ImmutableLongList tail;

        private NonEmptyList(final long head, final ImmutableLongList tail) {
            this.head = head;
            this.tail = tail;
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        @Override
        public long getHead() {
            return head;
        }

        @Override
        public ImmutableLongList getTail() {
            return tail;
        }
    }

    public static ImmutableLongList makeList(final int head, final ImmutableLongList tail) {
        return new NonEmptyList(head, tail);
    }
}

/**
 * @author User
 */
public class Main {

    final int kwota = 29;
    final int[] nominały = new int[]{12, 5, 7, 4, 1};
    final ImmutableLongList[] L = new ImmutableLongList[kwota + 1];
    final long[] W = new long[kwota + 1];
    final long pseudoInfinity = Long.MAX_VALUE;

    void run() throws Exception {
        Arrays.fill(L, ImmutableLongList.getEmpty());
        Arrays.fill(W, pseudoInfinity);
        W[0] = 0;
        for (final int nominał : nominały) {
            for (int i = nominał; i < W.length; i++) {
                if (W[i - nominał] != pseudoInfinity) {
                    if (W[i - nominał] + 1 < W[i]) {
                        W[i] = W[i - nominał] + 1;
                        L[i] = ImmutableLongList.makeList(nominał, L[i - nominał]);
                    }
                }
            }
            for (int i = 0; i < W.length; i++) {
                final long v = W[i];
                if (v == pseudoInfinity) {
                    System.out.print(" --, ");
                } else {
                    System.out.format("%3d, ", W[i]);
                }
            }
            System.out.println("objects count: " + objectsCount(L));
        }
        System.out.print("Change: ");
        for (final long nominał : L[kwota]) {
            System.out.println(nominał + ", ");
        }
        System.out.println();
        
    }
    
    long objectsCount(final ImmutableLongList[] lists) {
        final Set<ImmutableLongList> objects = new HashSet<ImmutableLongList>();
        long wynik = lists.length == 0 ? 0 : 1; // empty lists by default
        for (final ImmutableLongList list : lists) {
            ImmutableLongList currentHead = list;
            while (currentHead != ImmutableLongList.getEmpty()) {
                wynik += objects.add(currentHead) ? 1 : 0;
                currentHead = currentHead.getTail();
            }
        }
        return wynik;
    }

    public static void main(final String[] args) throws Exception {
        new Main().run();
    }
}