Copiado al portapapeles
Descripción
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 linea. EL primer numero
$(N \leq 6)$ es el numero de denominaciones de monedas disponibles. Siguen $N$ números separados por espacio y finalmente el monto de cambio $M \leq 1000$ que hay que dar. La entrada termina cuando no hay más datos.
Salida
Por cada caso de prueba escriba en la salida el mínimo numero de monedas que se requieren para dar cambio. Si no es posible dar cambio imprima "-1".
Ejemplo Entrada
6 1 5 10 25 50 100 289 1 100 300 3 1 5 25 100 3 100 50 5 89
Ejemplo Salida
9 3 4 -1