== include(page="template/taskheader" task_id="collar") ==
Tassadar a descoperit un colier Xel’Naga format din $N$ perle, fiecare perlă $i$ având asociat un coeficient $V{~i~}$, iar frumuseţea colierului este $max(V{~i~}, 1 ≤ i ≤ N) – min(V{~i~}, 1 ≤ i ≤ N)$. Tassadar vrea să împartă colierul în mai multe coliere de lungimi egale, astfel încat fiecare colier nou să reprezinte o subsecvenţă a colierului iniţial, fiecare perlă din colierul iniţial să facă parte din exact un colier nou, iar suma frumuseţilor colierelor noi să fie maximă.
Tassadar a descoperit un colier Xel’Naga format din $N$ diamante, fiecare diamant $i$ având asociat un număr de carate $V{~i~}$. Puterea magică oferită de un colier este $max(V{~i~}, 1 ≤ i ≤ N) – min(V{~i~}, 1 ≤ i ≤ N)$. El vrea să împartă colierul în mai multe coliere de lungimi *egale*, astfel încat să fie respectate următoarele condiţii:
Tassadar nu este un bijutier prea iscusit şi vă roagă pe voi să-i spuneţi care este suma frumuseţilor maximă pe care o poate obţine printr-o împărţire a colierului.
* fiecare colier nou să reprezinte o subsecvenţă a colierului iniţial
* fiecare perlă din colierul iniţial să facă parte din exact un colier nou
* suma puterilor oferite de colierele noi să fie maximă
Deoarece Tassadar nu este un bijutier prea iscusit, vă roagă pe voi să-i spuneţi care este puterea maximă pe care o poate obţine printr-o împărţire a colierului.
h2. Date de intrare
Fişierul de intrare $collar.in$ conţine pe prima linie numărul natural $N$ cu semnificaţia din enunţ. Pe linia următoare se află $N$ numere întregi $V{~i~}$ reprezentând coeficienţii perlelor.
Fişierul de intrare $collar.in$ conţine pe prima linie numărul natural $N$ cu semnificaţia din enunţ. Pe linia următoare se află $N$ numere întregi $V{~i~}$ reprezentând numărul de carate pentru fiecare diamant.
h2. Date de ieşire
În fişierul de ieşire $collar.out$ veţi afişa un singur număr, reprezentând frumuseţea maximă pe care o poate obţine Tassadar prin împărţirea colierului.
În fişierul de ieşire $collar.out$ veţi afişa un singur număr, reprezentând suma maximă a puterilor pe care o poate obţine Tassadar prin împărţirea colierului.
h2. Restricţii
* $1 ≤ N ≤ 65.536$
* $-1.000.000.000 ≤ V{~i~} ≤ 1.000.000.000$
* colierul iniţial este circular
* Colierul iniţial este circular
* Vă recomandăm să folosiţi numere întregi pe 64 de biţi cu semn
h2. Exemplu
