Pracsiu Dan (dnprx) Ion este un tânăr muzician și studiază chitara clasică. La un spectacol în aer liber, Ion a fost invitat să interpreteze câteva dintre piesele sale. Ion are în repertoriu n piese, a căror durată este t[1], t[2], …, t[n] și ştie că timpul care-i va fi alocat nu poate depăşi T unităţi de timp. Pentru alegerea pieselor, Ion este interesat să ştie câte variante distincte are de a interpreta cel puţin o piesă în spectacol, astfel încât durata totală a pieselor interpretate să nu depăşească T. Două variante sunt distincte dacă există cel puţin o melodie care se găseşte într-o variantă şi nu se găseşte în cealaltă variantă.
Cerința
Cunoscând n, T și duratele pieselor, determinaţi numărul de variante distincte pe care le are Ion de a interpreta piese astfel încât durata lor să nu depăşească T.
Date de intrare
Fișierul de intrare piese1.in conține pe prima linie numerele n şi T având semnificaţia din enunţ. Pe linia a doua se găsesc n numere naturale t[1], t[2], …, t[n], separate printr-un singur spaţiu, reprezentând duratele pieselor din repertoriul lui Ion.
Date de ieșire
Fișierul de ieșire piese1.out va conţine pe o singură linie un număr natural ce reprezintă numărul de variante distincte pe care le are Ion de a interpreta piese din repertoriul său, astfel încât durata lor să nu depăşească T.
Restricții și precizări
2 ≤ n ≤ 301 ≤ x1, x2, ..., xn, T ≤ 1 000 000 000- Ordinea de prezentare a pieselor în spectacol nu este relevantă.
Exemplul 1:
piese1.in
3 2 4 3 5
piese1.out
0
Explicație
Nu există nicio variantă. Toate piesele durează mai mult de T unități de timp.
Exemplul 2:
piese1.in
4 6 2 4 5 1
piese1.out
8
Explicație
Sunt 8 variante posibile: 2, 4, 5, 1, 2+4, 2+1, 4+1, 5+1.