Pentru un șir $x_1, x_2, \dots x_m$ de numere întregi, definim următorii termeni:

O subsecvență $(i, j)$ este șirul format din numerele $x_i, x_{i+1}, x_{i+2}, \dots x_j$ în această ordine.

Suma unei subsecvențe $(i, j)$ este suma valorilor din șir. Mai exact, $x_i + x_{i+1} + x_{i+2} + \dots x_j$.

O subsecvență este $k$-subsecvență dacă și numai dacă lungimea subsecvenței este divizibilă cu $k$.

Cerință

Se dă $n, k$ și un șir $a_1, a_2, \dots a_n$ de numere întregi. Să se afle suma maximă a unei $k$-subsecvențe.

Atenție! Aveți voie să alegeți o subsecvență de lungime $0$ (care are suma $0$). Deci răspunsul este cel puțin $0$.

Date de intrare

Pe prima linie a fișierului de intrare divk.in se găsesc două numere întregi, $n$ și $k$. Pe a doua linie se află șirul $a_1, a_2, \dots a_n$ de numere întregi.

Date de ieșire

Pe prima linie a fișierului de ieșire divk.out se va găsi un singur număr întreg, suma maximă a unei $k$-subsecvențe.

Restricții și precizări

• $1 \leq k \leq n \leq 1 \ 000 \ 000$
• $-10^9 \leq a_i \leq 10^9$ pentru fiecare $i$ de la $1$ la $n$.

Exemplul 1

divk.in

5 3
9 -1 8 4 -13

divk.out

16

Explicație

Avem $k = 3$.

Putem alege $3$-subsecvența $(1, 3)$ care are suma $9 + (-1) + 8 = 16$. Nu putem alege subsecvența $(1, 4)$ deoarece are lungimea $4$, iar $4$ nu e divizibil cu $3$.

Exemplul 2

divk.in

5 1
9 -1 8 4 -13

divk.out

20

Explicație

$k = 1$

Putem alege $1$-subsecvența $(1, 4)$. Aceasta are suma $9 + (-1) + 8 + 4 = 20$.

Exemplul 3

divk.in

7 3
-1 -1 -1 9 -1 -1 -1

divk.out

7

Explicație

$k = 3$

Există mai multe subsecvențe care obțin suma $7$. De exemplu, putem alege $3$-subsecvența $(3, 5)$. Aceasta are suma $(-1) + 9 + (-1) = 7$.

Exemplul 4

divk.in

3 2
-1 -1 -1

divk.out

0

Explicație

$k = 2$

Observăm că orice subsecvență de lungime $\geq 1$ are suma negativă. Deci, putem alege subsecvența vidă care are suma $0$.