Rezolvare PBinfo #4237

Mao, care a fost timp de 45 de ani fochist la Curtea Constituțională, s-a pensionat și s-a apucat de agricultură. El a tăiat n tulpini de bambus de dimensiuni d1, d2, …, dn și din ei vrea să obțină cel puțin A araci de lungime egală L, maxim posibilă.

Cerința

Să se determine lungimea maximă L pe care o poate obține pentru cel puțin A araci tăind bambușii.

Date de intrare

Programul citește de la tastatură numerele n și A, iar apoi n numere naturale, separate prin spații, reprezentând dimensiunile tulpinilor de bambus.

Date de ieșire

Programul va afișa pe ecran L, reprezentând lungimea maximă posibilă a celor cel puțin A araci.

Restricții și precizări

• 3 ≤ n ≤ 100.000
• 1 ≤ di ≤ 30.000
• d1, d2, …, dn, L și A sunt numere naturale nenule.
• Este garantat că se pot obține araci de lungime cel puțin 1.

Exemplu:

Intrare

5 7
10 12 4 2 16

Ieșire

5

Explicație

Cei 7 araci se pot tăia de dimensiune maximă 5: din bambusul de dimensiune 10 pot obține 2 araci, din cel de dimensiune 12 încă 2 araci, iar din cel de dimensiune 16 încă 3 araci. 2 + 2 + 3 = 7.