== include(page="template/taskheader" task_id="blackwater") ==

Esti Stannis Baratheon si incerci sa cuceresti King's Landing. Ataci prin portul orasului si dispui de $N$ barci in sir indian (prima este cea mai apropiata de port, apoi a doua e in spatele primei si tot asa). Fiecare barca are puterea ei de atac specifica, dar aceasta putere scade in functie de distanta barcii fata de port.

Stannis Baratheon incearcă să cucerească King's Landing. El atacă prin portul oraşului şi dispune de $N$ bărci in şir indian (prima este cea mai apropiată de port, apoi a doua e in spatele primei şi tot aşa). Fiecare barcă are puterea ei de atac specifică, dar aceasta putere scade în funcţie de distanţa bărcii faţă de port.

Daca puterile barcilor sunt vazute ca un vector de numere intregi, de exemplu $V = [3, 4, 2, 1, 5]$ atunci prima va lovi cu putere $3/1$, a doua cu putere $4/2 = 2$, a treia cu putere $2/3 = 0$, a patra cu putere $1/4 = 0$ si a cincea cu putere $5/5 = 1$. Asadar suma tuturor loviturilor date de barci este <tex>$V_{1}/1 + V_{2}/2 + V_{3}/3 + .. + V_{N}/N$</tex>.

Dacă puterile bărcilor sunt vazute ca un vector de numere întregi, de exemplu $V = [3, 4, 2, 1, 5]$ atunci prima va lovi cu putere $[3/1]$, a doua cu putere $[4/2] = 2$, a treia cu putere $[2/3] = 0$, a patra cu putere $[1/4] = 0$ si a cincea cu putere $[5/5] = 1$, unde $[x]$ este partea întreagă inferioară numărului $x$. Aşadar, suma tuturor loviturilor date de bărci este <tex>\lfloor{$V_{1}/1}\rfloor + \lfloor{V_{2}/2}\rfloor + \lfloor{V_{3}/3}\rfloor + .. + \lfloor{V_{N}/N$}\rfloor </tex>.

Stannis incepe lupta in curand, dar realizeaza ca poate creste suma loviturilor reorganizand barcile, dar el din cauza ca este grabit poate doar sa permute circular vectorul cu barci, de exemplu $[3, 4, 2, 1, 5]$ permutat circular la stanga de $2$ ori va rezulta in $[2, 1, 5, 4, 3]$. Care este suma maxima a loviturilor daca poti permuta circular la stanga de ori de cate ori vrei (eventual $0$ ori)?

Stannis începe lupta în curând, dar realizează că poate creşte suma loviturilor reorganizand bărcile, dar el, din cauza că este grabit, poate doar să permute circular vectorul cu bărci, de exemplu $[3, 4, 2, 1, 5]$ permutat circular la stânga de $2$ ori va rezulta în $[2, 1, 5, 3, 4]$. Care este suma maximă a loviturilor daca poti permuta circular la stânga de ori de câte ori vrei (eventual $0$ ori)?

h2. Date de intrare

* $1 ≤ n ≤ 80 000$
* $0 ≤ v[i] ≤ 100 000$

* Pentru 10% din punctajul problemei se asigura ca $1 ≤ n ≤ 5000$
* Pentru alte 10% din punctajul problemei se asigura ca $1 ≤ k ≤ 5000 unde k este numarul de elemente nenule$
* Pentru alte 15% din punctajul problemei se asigura ca valorile elementelor vor fi doar 0 sau 100 000$

* Pentru $11$ puncte se asigura ca $1 ≤ n ≤ 5000$
* Pentru $10$ puncte se asigura ca $1 ≤ k ≤ 5000 unde k este numarul de elemente nenule$
* Pentru alte $16$ puncte se asigura ca valorile elementelor vor fi doar $0$ sau $100 000$

h2. Exemplu

| 5
3 4 2 1 5
|7

|
| 3
100000 0 100000
|150000

|
h3. Explicaţie

$[3, 4, 2, 1, 5]$ permutat la stanga de $4$ ori va rezulta $[5, 3, 4, 2, 1]$ -> $5/1+3/2+4/3+2/4+1/5 = 5+1+1+0+0 = 7$

$[3, 4, 2, 1, 5]$ permutat la stanga de $4$ ori va rezulta $[5, 3, 4, 2, 1]$ -> $[5/1] + [3/2] + [4/3] + [2/4] + [1/5] = 5 + 1 + 1 + 0 + 0 = 7$
$[100000, 0, 100000]$ permutat la stanga de $2$ ori va rezulta $[100000, 100000, 0]$ -> $[100000/1] + [100000/2] + [0/3] = 100000 + 50000 + 0 = 150000$

== include(page="template/taskfooter" task_id="blackwater") ==