Minimizando monedas


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
Assembly, Awk, Brain****, C, C++, Java, Pascal, Perl, Python, Sed, Text

Minimizando monedas

En CSESlandia utilizan un sistema monetario que consiste en \(n\) tipos de monedas, cada una con un valor entero positivo. Para estudiar que tan óptimo es el sistema monetario del pais se desea conocer cuantas monedas serían necesarias como mínimo para juntar una suma estandar \(x\) de dinero.

Por ejemplo, si las monedas tienen un valor de \(\{1,5,7\}\) y la suma estandar es \(x=11\), una forma de juntar \(x\) con la menor cantidad de monedas sería \(5+5+1=11\).

Entrada

La primera linea contiene dos enteros \(n\) y \(x\), el numero de monedas y la suma estandar, respectivamente (\(1\leq n \leq 100, 1 \leq x \leq 10^6\)).

La segunda linea contiene \(n\) enteros distintos \(c_1,c_2,\dots,c_n\), el valor de cada moneda (\(1 \leq c_i \leq 10^6\), para cada \(1 \leq i \leq n\)).

Salida

Imprimir un solo número: la menor cantidad de monedas necesarias. Si no es posible producir la suma estandar \(x\), imprimir \(-1\).

Ejemplo

Entrada

3 11
1 5 7

Salida

3

Comments

There are no comments at the moment.