V = [1, 3, 4]
S = 9
Puhver={0:0}

def leiaKogus(S):
    if S < 0: return 100000
    if S in Puhver: return Puhver[S]
    vastus = 100000
    for i in V:
        vastus = min(vastus, 1 + leiaKogus(S - i))
    Puhver[S]=vastus
    return vastus

print(leiaKogus(S))