scuderia

Anul ăsta e anul nostru...

Figura 1 din enunțul original al problemei scuderia.Mărește schema ↗

Spun fanii Scuderiei - cea mai iubită echipă de Formula 10 - deja de prea mulți ani. Dar anul acesta chiar e diferit, deoarece se schimbă regulamentul tehnic, iar cei doi piloți ai echipei, Carol și Luis, sunt motivați să aducă înapoi gloria demult uitată a echipei.

Înainte de prima cursă din sezon, Marele Premiu al orașului Necleab, Carol și Luis pot să facă mașina mai rapidă folosindu-se de un șir de $n$ numere întregi, indexat de la $0$ la $n - 1$, și patru numere: $k$, $p$, $q$ și $r$.

Carol selectează o mulțime care conține indicii unei subsecvențe de lungime $q \cdot k$ din șirul de $n$ numere. Indicele de start al acestei subsecvențe, notat cu $i$, trebuie să îndeplinească condiția $i \text{ \% } k = r$. Spre exemplu, pentru $n = 25$, $k = 6$, $q = 2$ și $r = 3$, o posibilă selecție a lui Carol este $\{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}$.

Luis selectează inițial o mulțime care conține indicii unei subsecvențe de lungime $p$ din șirul de $n$ numere. Ulterior, el adaugă indici astfel încât, la final, un indice $i$ aparține mulțimii dacă și numai dacă indicele $i + k$ aparține aceleiași mulțimi, ori de câte ori ambii indici sunt cuprinși între $0$ și $n - 1$. Spre exemplu, pentru $n = 15$, $k = 6$, și $p = 3$, dacă Luis selectează inițial mulțimea cu indicii $\{1, 2, 3\}$, la final aceasta va fi $\{1, 2, 3, 7, 8, 9, 13, 14\}$.

După alegerea mulțimilor, Carol și Luis le reunesc. Dacă un indice se află în ambele mulțimi, acesta va fi luat o singură dată în considerare. Viteza mașinii crește cu o valoare egală cu suma numerelor din șirul inițial care au indicii în mulțimea finală.

Cerință

Pentru ca în sfârșit anul ăsta să fie anul lor, piloții vor să facă mașina cât mai rapidă. Urmând regulile descrise mai sus, care este viteza maximă cu care piloții pot îmbunătăți mașina?

Date de intrare

Fișierul de intrare scuderia.in conține pe prima linie 5 numere întregi $n$, $k$, $p$, $q$ și $r$, cu semnificația din enunț. A doua linie conține cele $n$ elemente ale șirului.

Date de ieșire

Pe prima linie a fișierului de ieșire scuderia.out se va afișa un singur număr, reprezentând valoarea maximă pe care o pot obține piloții.

Restricții și precizări

• $1 \leq n \leq 1 \ 000 \ 000$
• $1 \leq k < 100 \ 000$
• $k < n$
• $0 \leq p, q \leq n$
• $0 \leq r < k$
• $0 \leq r + q \cdot k < n$
• Numerele din șir se află în intervalul $[-1 \ 000, 1 \ 000]$
• O subsecvență de lungime $l$, $0 \leq l \leq n$, a șirului este un șir format din $l$ elemente aflate pe poziții consecutive în șirul inițial.
• Operatorul % reprezintă operația modulo, adică restul împărțirii a două numere întregi.
• Rezultatul final poate fi și un număr negativ. Asta înseamnă că mașina devine mai înceată decât era inițial, un lucru pe care scuderia reușește cumva să-l facă uneori...
• Atenție la limita de memorie!

Exemplul 1

scuderia.in

9 3 0 1 0
10 6 7 5 20 5 1 8 3

scuderia.out

30

Explicație

$k = 3$, $p = 0$, $q = 1$, $r = 0$. Deoarece $p = 0$, Luis nu va selecta niciun indice, deci doar Carol îmbunătățește viteza mașinii, alegând o subsecvență de lungime $3 \cdot 1 = 3$. Aceasta conține indicii $3$, $4$, și $5$. $3 \text{ \% } 3 = 0$, și obține suma $5 + 20 + 5 = 30$, care este maximă.

Exemplul 2

scuderia.in

9 3 2 0 0
10 6 7 5 20 5 1 8 3

scuderia.out

50

Explicație

$k = 3$, $p = 2$, $q = 0$, $r = 0$. Deoarece $q = 0$, Carol nu va selecta niciun indice, deci doar Luis îmbunătățește viteza mașinii. Inițial, alege $p = 2$ indici: $\{0, 1\}$, după care adaugă alți indici, ajungând la final cu mulțimea $\{0, 1, 3, 4, 6, 7\}$. Viteza va crește cu $10 + 6 + 5 + 20 + 1 + 8 = 50$, care este maximă.

Exemplul 3

scuderia.in

9 3 2 1 0
10 6 7 5 20 5 1 8 3

scuderia.out

59

Explicație

$k = 3$, $p = 2$, $q = 1$, $r = 0$, deci ambii piloți îmbunătățesc viteza mașinii. Mulțimea aleasă de Carol este $\{0, 1, 2\}$, iar mulțimea finală a lui Luis este $\{1, 2, 4, 5, 7, 8\}$. În total, viteza crește cu $10 + 6 + 7 + 20 + 5 + 8 + 3 = 59$, care este maximă.

Exemplul 4

scuderia.in

9 3 2 1 1
-3 -2 -9 -47 -4 -5 -92 -8 -17

scuderia.out

-92

Explicație

$k = 3$, $p = 2$, $q = 1$, $r = 1$, deci ambii piloți îmbunătățesc viteza mașinii. Mulțimea aleasă de Carol este $\{1, 2, 3\}$, iar mulțimea finală a lui Luis este $\{1, 2, 4, 5, 7, 8\}$. În total, viteza crește cu $-2 - 9 - 47 - 4 - 5 - 8 - 17 = -92$, care este maximă. În această situație, mașina devine mai înceată.