Dar Cambio

Por Jorge Teran

Se están implementando máquinas para dar cambio. Las monedas disponibles en el país son de
1,5,10,25,50, y 100 centavos.

Las máquinas expendedoras de cambio tienen de 1 a 6  bolsillos para colocar monedas. Para reducir la cantidad de monedas que se utilizan al dar cambio, te piden calcular el mínimo de monedas requeridas.

Por ejemplo, si tenemos las 6 denominaciones, y hay que dar cambio de 289 pesos daremos 2 monedas de 100 centavos,
1 de 50 centavos, 1 de 25 centavos, 1 de 10 y 4 de 1 centavos, esto es 2*100+1*50+1*25+1*10+4=289 que son un total de 9  monedas.

Las únicas denominaciones posibles son las anteriormente citadas.

Entrada

La entrada consiste en múltiples casos de prueba. Cada caso de prueba consta de una línea. El primer número
(N <= 6) es el número de denominaciones de monedas disponibles. Siguen N números separados por espacio y finalmente el monto de cambio M <= 1000 que hay que dar. La entrada termina cuando no hay más datos.

Salida

Por cada caso de prueba escriba en la salida,una línea con el mínimo número de monedas que se requieren para dar cambio. Si no es posible dar cambio imprima "-1".

Ejemplo de Entrada

6 1 5 10 25 50 100 289
1 100 300
3 1 5 25 100
3 100 50 5 89

Ejemplo de Salida

9
3
4
-1

Código

DARCAMBIO

Intentos de resolución

61
40

Logrados

Etiquetas

#obi-departamental