Canvi mínim P81009

Donada una quantitat c, i n valors diferents de monedes, de cadascun dels quals se’n disposa de tantes com es vulgui, calculeu quin és el mínim nombre de monedes que sumen canvi c. Per exemple, si c = 20 i podem triar entre els valors 2, 4, 6 i 17, es pot aconseguir c només amb quatre monedes: 2 + 6 + 6 + 6 = 20.

Entrada

L’entrada consisteix en diversos casos, cadascun amb c i n, seguits d’n naturals diferents entre 1 i 10⁴. Suposeu que c està entre 0 i 10⁴, i que n està entre 1 i 1000.

Sortida

Per a cada cas, escriviu el mínim nombre de monedes que tenen suma c. Si no n’hi ha cap, escriviu “no”.