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^4$. Suposeu que $c$ està entre 0 i $10^4$, 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”.