read = 0
coin_values =[]

# Быстрая сортировка массива
def partition(arr,low,high):
    i = ( low-1 )
    pivot = arr[high]
    for j in range(low , high):
        if arr[j] <= pivot:
            i = i+1
            arr[i],arr[j] = arr[j],arr[i]
    arr[i+1],arr[high] = arr[high],arr[i+1]
    return ( i+1 )


def quickSort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
#


def money(coins_list,change,min_coins,coins_used):
    for c in range(change+1):
        coin_count = c
        new_coin = coins_list[0]
        for j in coins_list:
            if j <= c:
                if min_coins[c-j] + 1 < coin_count:
                    coin_count = min_coins[c-j]+1
                    new_coin = j
            min_coins[c] = coin_count
            coins_used[c] = new_coin
    return min_coins[change]

def print_coins(coins_used,change):
    coin = change
    while coin > 0:
        this_coin = coins_used[coin]
        print(this_coin)
        coin = coin - this_coin



#Ввод данных
while True:
    print("Введите номинал монеты. Для выхода введите stop : ")
    read = input();

    if read.isdigit():
        coin_values.append(int(read))
    elif read == "stop":
        break
    else:
        print("Неверное значение! Введите число или stop.")

while True:
    print("Введите сумму : ")
    read = input()

    if read.isdigit():
        summ = int(read)
        break
    else:
        print("Неверное значение! Введите число.")

#


quickSort(coin_values,0,len(coin_values)-1)
coins_used = [0]*(summ+1)
coin_count = [0]*(summ+1)

print(" монет  : ",money(coin_values,summ,coin_count,coins_used))
print_coins(coins_used,summ)
print()
print(coins_used)
print(coin_count)