Candale Silviu (silviu) Marian are un pachet cu n bețișoare, fiecare bețișor i având lungimea a[i] cm. Bețișoarele au o proprietate special: bețișorul cu numărul i se poate conecta de bețișorul i+1, unde i este mai mic decât n. Spre exemplu, într-un pachet cu 10 bețișoare, primul se poate conecta la al doilea, al doilea la al treilea, și așa mai departe. În momentul unei conectări, lungimea bețișorului devine suma lungimilor celor două bețișoare care l-au compus. Marian repetă acest procedeu până când are exact k bețișoare.
Cerința
Să se determine cea mai mare lungime L posibilă, astfel încât toate cele k bețișoare obținute să aibă lungimea mai mare sau egală cu L.
Date de intrare
Fișierul de intrare betisoare.in conține pe prima linie numerele n k. A doua linie conține n numere, reprezentând lungimile fiecărui bețișor.
Date de ieșire
Fișierul de ieșire betisoare.out va conține un număr, reprezentând valoarea lui L.
Restricții și precizări
1 ≤ n, k ≤ 1 000 0001 ≤ a[i] ≤ 1 000- pentru teste în valoare de 7 puncte,
n = k; - pentru alte teste în valoare de 11 puncte,
k = 2; - pentru alte teste în valoare de 13 puncte,
n < 1000, k = 3; - pentru alte teste în valoare de 15 puncte,
n < 100, k = 4; - pentru alte teste în valoare de 54 de puncte, nu există alte restricții.
Exemplu:
betisoare.in
8 3 7 2 5 3 9 2 4 9
betisoare.out
13
Explicație
Primele 3 bețișoare adunate obțin lungimea 7 + 2 + 5 = 14
Următoarele 3 bețișoare adunate obțin lungimea 3 + 9 + 2 = 14
Ultimele două bețișoare adunate obțin lungimea 4 + 9 = 13
Așadar, răspunsul este 13.