Gogosi

Cerință

Marius vrea să invite mai mulți prieteni acasă. Pe masă se află $N \le 500 \ 000$ gogoși, fiecare având asociată o valoare naturală. Marius nu își amintește exact câți prieteni are, dar știe că are cel puțin un prieten.

El definește un scenariu, reprezentat de un număr $k$, astfel încât, dacă ar chema $k$ prieteni, fiecare persoană (inclusiv Marius) ar mânca același număr de gogoși, fără să rămână vreo gogoasă pe masă. În fiecare scenariu, gogoșile sunt împărțite consecutiv:

• primul prieten primește primele $N / (k + 1)$ gogoși.
• al doilea următoarele $N / (k + 1)$, și așa mai departe.
• etc... (Cele $N$ gogoși se împart la $k+1$ deoarece vor mânca Marius și cei $k$ prieteni)

Întrebarea lui Marius este: care este suma maximă a valorilor gogoșilor pe care le poate mânca unul dintre băieți în oricare scenariu posibil?

Date de intrare

Pe prima linie se află un număr natural $N$.

Pe a doua linie se află $N$ numere naturale reprezentând valorile gogoșilor $v_1, v_2, \dots, v_N$.

Date de ieșire

Pe o singură linie se va afișa un număr natural: suma maximă a valorilor gogoșilor pe care le poate primi unul dintre băieți.

Restricții și precizări

• $1 \leq N \leq 500 \ 000$
• $1 \leq v_i \leq 1 \ 000 \ 000 \ 000$
• Numărul de prieteni $k \geq 1$

Exemplu

stdin

6
7 2 10 5 3 2

stdout

19

Explicație

Marius poate chema 1 prieten (deci $k = 1$). Primul prieten primește primele 3 gogoși cu valorile 7, 2 și 10, suma acestora fiind 19. Cel de-al doilea prieten primește gogoșile cu valorile 5, 3 și 2, suma valorilor fiind 10. Maximul este atins de primul prieten, care va avea suma 19.