Python - ATM, Banknotes and their count

Another day, another issues while studying Python.

This time, i need to create some kind of ATM program, user enters number of money he/she wants to take out, while balance is random in range (100-500), i didn't connect this to each other yet, but it works right now.

The problem begins with the second part of the task, as i said i get balance as random in range (100-500), I need to take this random number and split it randomly with banknotes, for example if my number is 150, i can get different answers like this (Note: I have nominal banknotes (50, 20, 10, 5)):

150$ = 3 x 50$, 0 x 20$, 0 x 10$, 0 x 5$
or
150$ = 2 x 50$, 0 x 20$, 5 x 10$, 0 x 5$
or
150$ = 2 x 50$, 1 x 20$, 2 x 10$, 2 x 5$

It should be random, so to say in short my task is:

User enters number(Money) which he/she want to take out, balance is random in range (100-500), in the background, program calculates all the possible way of divisions of banknotes and gives me one of them (Print), that i have for example 2 50$ banknotes, 10 20$ banknotes and etc. In the end program chooses the way to give out the money with the least number of banknotes.

Here is my code, this is the maximum i could do :

from random import randint
S = int(input("Amount of money you want to take: "))
Banknote = [50, 20, 10, 5]
balance = randint(100, 500)
print("Your Balance: ",balance, " \n 50 Banknote count: ", int(balance/50))
print(" 20 Banknote count: ", int((balance - int(balance/50)*50)/20))

Can't randomly choose those banknotes, so i used another method, but this one is totally NOT right.

Please, any help.