Râme pane

Time limit: 0.1s Memory limit: 64MB Input: Output:

Chef Constantin a primit comandă de MM râme pane, specialitatea casei. El se uită în cufărul de râme și observă că are la dispoziție NN râme, de lungimi întregi r1,r2,,rNr_1, r_2, \dots, r_N.

Chef iscusit, Constantin poate tăia râmele în bucăți mai mici de lungime întreagă. Apoi acesta prăjește câte o râmă (sau bucată de râmă) pentru fiecare dintre cei MM oaspeți. Satisfacția unui oaspete este dată de lungimea râmei primite iar satisfacția lui Constantin, om empatic, este minimul satisfacțiilor tuturor clienților săi.

Cerință

Dacă taie și distribuie râmele în mod optim, care este satisfacția maximă pe care o poate avea Chef Constantin?

Date de intrare

Pe prima linie din standard input se dau două numere NN și MM, cu semnificația din enunț.

Următoarea linie conține NN numere: r1,r2,,rNr_1, r_2, \dots , r_N .

Date de ieșire

Pe singura linie din standard output se va afișa un singur număr, satisfacția maximă a lui Chef Constantin. Dacă nu există nicio împărțire posibilă, atunci satisfacția lui este 00.

Restricții și precizări

  • 1N,M1051 \leq N, M \leq 10^5
  • 1ri106,  1iN1 ≤ r_i ≤ 10^6,\ \forall\ 1 ≤ i ≤ N
# Punctaj Restricții
1 15 M=2M = 2
2 15 N=2N = 2
3 40 1N,M1031 \leq N, M \leq 10^3, 1ri103,  1iN1 ≤ r_i ≤ 10^3, \ \forall\ 1 ≤ i ≤ N
4 30 Fără restricții suplimentare

Exemplul 1

stdin

1 2
255

stdout

127

Exemplul 2

stdin

10 6
15 43 72 59 18 8 24 97 61 27

stdout

43

Log in or sign up to be able to send submissions!