Rezolvare PBinfo #4266

Cerința

Fie un număr natural s și un șir de n numere naturale nenule. Să se determine suma maximă posibilă, mai mică sau egală cu s ce se poate obține dintr-un subșir al șirului.

Date de intrare

Programul citește de la tastatură numărul n și s, apoi n numere naturale, separate prin spații, reprezentând elementele șirului.

Date de ieșire

Programul va afișa pe ecran numărul M, reprezentând suma maximă posibilă, mai mică sau egală cu s ce se poate obține dintr-un subșir al șirului.

Restricții și precizări

• 3 ≤ n ≤ 40
• 1 ≤ s ≤ 2.000.000.000
• Șirul va conține numere naturale nenule mai mici decât 50.000.001.
• Toate elementele șirului vor fi mici sau egale decât s.

Exemplul 1:

Intrare

5 20
5 10 6 8 3

Ieșire

19

Explicație

Suma maximă mai mică sau egală decât 20 este 19 și se formează din 10, 6 și 3.

Exemplul 2:

Intrare

5 20
17 16 10 12 14

Ieșire

17

Explicație

Suma maximă mai mică sau egală decât 20 este 17 și se formează doar din numărul 17.