Ifri y el arreglo.


Submit solution


Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++

Ifri estaba estudiando programación y le dieron ganas de jugar con arreglos. Después de jugar solo todo el día comenzó a aburrirse, así que llamó a su amigo Torvic para que le propusiera algo nuevo. Torvic le planteó el siguiente problema:

Dado un arreglo de n números, ¿de cuántas formas puedes elegir un subconjunto de este tal que la suma sea x?

Ifri cree que es un problema interesante, así que te llamó también a ti para que te diviertas con él.

Entrada

La primera línea de la entrada tiene dos números: n (1 \leq n \leq 40) y x (1 \leq x \leq 10^9), el tamaño del arreglo y la suma requerida, respectivamente.

La segunda línea contiene n enteros t_1,t_2,\dots,t_n (1 \leq t_i \leq 10^9): los números en el arreglo.

Salida

El número de formas en que puedes crear la suma x.

Ejemplo de Entrada

4 5
1 2 3 2

Ejemplo de Salida

3

Comments

There are no comments at the moment.