Anul ăsta e anul nostru…
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 · k din șirul de n numere. Indicele de start al acestei subsecvențe, notat cu i, trebuie să îndeplinească condiția 𝑖 % 𝑘 = 𝑟. Spre exemplu, pentru 𝑛 = 25, 𝑘 = 6, 𝑞 = 2 și 𝑟 = 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 𝑝 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 𝑖 + 𝑘 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ța

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 𝑛 elemente ale șirului.

Date de ieșire

Fișierul de ieșire scuderia.out va conține pe prima linie un singur număr, reprezentând valoarea maximă pe care o pot obține piloții.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• 1 ≤ k < 1.000
• k < n
• 0 ≤ p, q < n
• 0 ≤ r < k
• 0 ≤ r + q • k < n
• Numerele din șir se află în intervalul [-1.000, 1.000]
• O subsecvență de lungime l, 0 ≤ l ≤ 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!
• Pentru 10 puncte, k = 1
• Pentru 8 puncte, 𝑝 = 0, 1 ≤ 𝑛 ≤ 1.000
• Pentru 15 puncte, 𝑝 = 0
• Pentru 13 puncte, 𝑞 = 0, 𝑝 = 1
• Pentru 7 puncte, 𝑞 = 0, 1 ≤ 𝑘 ≤ 1.000
• Pentru 12 puncte, 𝑞 = 0
• Pentru 7 puncte, 𝑞 = 1, 𝑝 = 1
• Pentru 5 puncte, r = 0, 1 ≤ n ≤ 100
• Pentru 7 puncte, 𝑟 = 0
• Pentru 6 puncte, 1 ≤ n ≤ 100
• Pentru 10 puncte, fără restricții suplimentare

Exemplul 1:

scuderia.in

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

scuderia.out

30

Explicație

𝑘 = 3, 𝑝 = 0, 𝑞 = 1, 𝑟 = 0. Deoarece 𝑝 = 0, Luis nu va selecta niciun indice, deci doar Carol îmbunătățește viteza mașinii, alegând o subsubsecvență de lungime 3 ∗ 1 = 3. Aceasta conține indicii 3, 4, și 5. 3 % 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

𝑘 = 3, 𝑝 = 2, 𝑞 = 0, 𝑟 = 0. Deoarece 𝑞 = 0, Carol nu va selecta niciun indice, deci doar Luis îmbunătățește viteza mașinii. Inițial, alege 𝑝 = 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

𝑘 = 3, 𝑝 = 2, 𝑞 = 1, 𝑟 = 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

𝑘 = 3, 𝑝 = 2, 𝑞 = 1, 𝑟 = 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ă.