divk

Task

For a sequence $x_1, x_2, \dots x_m$ of integers, we define the following terms:

A subarray $(i, j)$ is the sequence formed by the numbers $x_i, x_{i+1}, x_{i+2}, \dots x_j$ in this order.

The sum of a subarray $(i, j)$ is the sum of the values in the sequence. More precisely, $x_i + x_{i+1} + x_{i+2} + \dots x_j$.

A subarray is a $k$-subarray if and only if the length of the subarray is divisible by $k$.

Task

Given $n$, $k$, and a sequence $a_1, a_2, \dots a_n$ of integers, find the maximum sum of a $k$-subarray.

Note! You are allowed to choose a subarray of length $0$ (which has a sum of $0$). Therefore, the answer is at least $0$.

Input data

The first line of the input file divk.in contains two integers, $n$ and $k$. The second line contains the sequence $a_1, a_2, \dots a_n$ of integers.

Output data

The first line of the output file divk.out will contain a single integer, the maximum sum of a $k$-subarray.

Constraints and clarifications

• $1 \leq k \leq n \leq 1\,000\,000$
• $-10^9 \leq a_i \leq 10^9$ for each $i$ from $1$ to $n$.

Example 1

divk.in

5 3
9 -1 8 4 -13

divk.out

16

Explanation

We have $k = 3$.

We can choose the $3$-subarray $(1, 3)$ which has the sum $9 + (-1) + 8 = 16$. We cannot choose the subarray $(1, 4)$ because its length is $4$, and $4$ is not divisible by $3$.

Example 2

divk.in

5 1
9 -1 8 4 -13

divk.out

20

Explanation

$k = 1$

We can choose the $1$-subarray $(1, 4)$. It has the sum $9 + (-1) + 8 + 4 = 20$.

Example 3

divk.in

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

divk.out

7

Explanation

$k = 3$

There are multiple subarrays that obtain the sum $7$. For example, we can choose the $3$-subarray $(3, 5)$. It has the sum $(-1) + 9 + (-1) = 7$.

Example 4

divk.in

3 2
-1 -1 -1

divk.out

0

Explanation

$k = 2$

We observe that any subarray of length $\geq 1$ has a negative sum. Therefore, we can choose the empty subarray which has a sum of $0$.