Fişierul intrare/ieşire:buget.in, buget.outSursăFMI No Stress 6
AutorAlex PalcuieAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.2 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/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 < 105
  • 1 ≤ B < 1015
  • 0 ≤ P[i] < 109 oricare 1 ≤ i ≤ n
  • B < Suma(P[i])
  • Toate examenele trebuie plătite.

Exemplu

buget.inbuget.out
5 30
1 7 5 9 10
8

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?