Fişierul intrare/ieşire:	buget.in, buget.out	Sursă	FMI No Stress 6
Autor	Alex Palcuie	Adăugată de	FMI No Stress •fmins123
Timp execuţie pe test	0.1 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Buget

Marian Buzdugan s-a hotărât să finalizeze "Facultatea de Informatică şi Care Era Cealaltă Chestie?" iar pentru asta trebuie să îşi mărească N examene.
Din fericire, măririle se plătesc în lei grei. Petre Căpraru, vâlcean fiind de meserie, a obţinut peste noapte sponsorizări pentru un buget în valoare de B lei (atenţie, sunt lei grei).

Fiecare examen de mărire are un preţ caracteristic P[i] (nu neapărat unic). Petre i-a sugerat lui Marian să nu plătească mai mult de C lei pentru fiecare examen pentru că mai există şi alte sesiuni de re-re-re-examinări. Marian a fost de acord dar şi-a propus să folosească un număr cât mai mare de lei din cei B oferiţi de Petre.

Ajutaţi-l pe Marian să găsească C-ul potrivit pentru a cheltui cât mai mult din cei B lei grei oferiţi de Petre.

Date de intrare

Fişierul de intrare buget.in conţine pe prima linie 2 numere separate prin câte un spaţiu, N şi B, cu semnificaţiile din enunt. Pe următoarea linie se vor afla N elemente separate prin spaţiu, reprezentând preţul P[i] celor N măriri.

Date de ieşire

Pe prima linie a fisierului buget.out se va scrie numărul căutat.

Restricţii

• 1 ≤ N < 10⁵
• 1 ≤ B < 10¹⁵
• 0 ≤ P[i] < 10⁹ oricare 1 ≤ i ≤ n
• B < Suma(P[i])
• Toate examenele trebuie plătite.

Exemplu

Explicaţie

Pentru limita C = 1 şirul preţurilor va fi [1,1,1,1,1] iar suma este 5.
Pentru limita C = 8 şirul preţurilor va fi [1,7,5,8,8] iar suma este 29.
Astfel pentru limita C = 8 suma va fi maximă dar totusi ≤ B

Cum se trimit solutii?