Buffet Table

Time limit1sMemory limit1024 MB

Summary

On a circle of N trays, a walker repeatedly jumps K steps clockwise, collecting each visited tray once until it revisits a tray; find the start that maximizes the total.

Level: Medium6 of 10
Topics: Number theory, Math, Implementation, Array
Solved: No attempts yet

Problem

Chocolate is said to boost brain activity. That is why the wise professor Trinidad Itobagovitš never misses a chance to treat himself to chocolate candies.

While relaxing at a ski resort during the school break, Trinidad found a wonderful café that serves a buffet breakfast. On one large round table there are $N$ trays, each holding some chocolate candies. Every morning, tray number $i$ receives $A_i$ candies. The trays are numbered $1, 2, \dots, N$ clockwise, and tray number $N$ is again followed by tray number $1$ .

As a great chocolate lover, Trinidad would happily eat every candy on the table, but manners and social pressure will not let him. So he picks an integer $K$ and, walking around the table in a circle, takes all the candies from every $K$ -th tray. That is, Trinidad goes to some tray and takes all of its candies; then he moves clockwise along the edge of the table and, counting $K$ trays forward from the tray he is currently at, reaches the next tray and takes all of its candies as well, continuing in the same way. When the next tray he would take candies from is already empty (because he has already stopped there), he stops collecting and begins to eat. Since Trinidad has breakfast very early, you may assume that no one else is taking candies from the trays at the same time.

Clearly, the number of candies collected depends on which tray Trinidad starts from. He may start at any tray, but he does not know which starting tray will let him collect the most candies. Help him find the maximum number of candies he can collect.

Input

The first line contains two space-separated integers $N$ and $K$ ( $2 \le K \le N \le 10^5$ ): the number of trays and the integer chosen by Trinidad, respectively. The second line contains $N$ integers $A_i$ ( $1 \le A_i \le 10^4$ , $i \in 1, \dots, N$ ), where $A_i$ is the number of candies on tray number $i$ .

Output

Output a single integer: the maximum number of candies Trinidad can collect in one pass around the buffet table.

Examples4

Example 1
Input
```
6 4
1 2 3 6 5 4
```
Expected output
```
12
```
Example 2
Input
```
6 3
1 2 3 6 5 4
```
Expected output
```
7
```
Example 3
Input
```
5 5
3 1 4 1 5
```
Expected output
```
5
```
Example 4
Input
```
5 2
3 1 4 1 5
```
Expected output
```
14
```