This morning, Roman woke up and opened the browser with n opened tabs numbered from 1 to n. There are two kinds of tabs: those with the information required for the test and those with social network sites. Roman decided that there are too many tabs open so he wants to close some of them.

He decided to accomplish this by closing every k-th (2 ≤ k ≤ n - 1) tab. Only then he will decide whether he wants to study for the test or to chat on the social networks. Formally, Roman will choose one tab (let its number be b) and then close all tabs with numbers c = b + i ⋅ k that satisfy the following condition: 1 ≤ c ≤ n and i is an integer (it may be positive, negative or zero).

For example, if k = 3, n = 14 and Roman chooses b = 8, then he will close tabs with numbers 2, 5, 8, 11 and 14.

After closing the tabs Roman will calculate the amount of remaining tabs with the information for the test (let's denote it e) and the amount of remaining social network tabs (s). Help Roman to calculate the maximal absolute value of the difference of those values |e - s| so that it would be easy to decide what to do next.

Input

The first line contains two integers n and k (2 ≤ k < n ≤ 100) — the amount of tabs opened currently and the distance between the tabs closed.

The second line consists of n integers, each of them equal either to 1 or to -1. The i-th integer denotes the type of the i-th tab: if it is equal to 1, this tab contains information for the test, and if it is equal to -1, it's a social network tab.

Output

Output a single integer — the maximum absolute difference between the amounts of remaining tabs of different types |e - s|.

Examples

Input


4 2
1 1 -1 1


Output


2


Input


14 3
-1 1 -1 -1 1 -1 -1 1 -1 -1 1 -1 -1 1


Output


9

Note

In the first example we can choose b = 1 or b = 3. We will delete then one tab of each type and the remaining tabs are then all contain test information. Thus, e = 2 and s = 0 and |e - s| = 2.

In the second example, on the contrary, we can leave opened only tabs that have social networks opened in them.
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws Exception {
        new Main().solve();
    }
    private void solve() throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int n=in.nextInt(),k=in.nextInt();
        int ans=0,a[]=new int[n],x1=0,y1=0;
        for(int i=0;i<n;i++) {
            a[i] = in.nextInt();
            if(a[i]==1)x1++;
            else y1++;
        }
        for(int i=0;i<k;i++){
            int x=0,y=0;
            for(int j=i;j<n;j+=k){
                if(a[j]==1)x++;
                else y++;
            }
            ans=Math.max(ans,Math.abs((x1-x)-(y1-y)));
        }
        out.println(ans);
        out.flush();
    }
}
class InputReader {
    private InputStreamReader reader;
    private char[] buf;
    private int len, now;

    public InputReader(InputStream stream) {
        reader = new InputStreamReader(stream);
        buf = new char[1024];
        len = 0;
        now = 0;
    }

    public String next() throws IOException {
        if (!hasNext()) throw new NullPointerException();
        StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(buf[now])) {
            sb.append(buf[now]);
            if (!move()) break;
        }
        return sb.toString();
    }

    public int nextInt() throws IOException {
        if (!hasNext()) throw new NullPointerException();
        boolean x = false;
        if (buf[now] == '-') {
            x = true;
            if (!move()) throw new NumberFormatException();
        }
        int ans = 0;
        while (!isSpaceChar(buf[now])) {
            if (isNum(buf[now])) ans = ans * 10 + buf[now] - '0';
            else throw new NumberFormatException();
            if (!move()) break;
        }
        return (x ? -1 : 1) * ans;
    }

    public String nextLine() throws IOException {
        if (!hasNextLine()) throw new NullPointerException();
        StringBuilder sb = new StringBuilder();
        while (buf[now] != '\n') {
            sb.append(buf[now]);
            if (!move()) return sb.toString();
        }
        now++;
        return sb.toString();
    }

    public long nextLong() throws IOException {
        if (!hasNext()) throw new NullPointerException();
        boolean x = false;
        if (buf[now] == '-') {
            x = true;
            if (!move()) throw new NumberFormatException();
        }
        long ans = 0;
        while (!isSpaceChar(buf[now])) {
            if (isNum(buf[now])) ans = ans * 10 + buf[now] - '0';
            else throw new NumberFormatException();
            if (!move()) break;
        }
        return (x ? -1 : 1) * ans;
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public int nextHexInt() throws IOException {
        if (!hasNext()) throw new NullPointerException();
        boolean x = false;
        if (buf[now] == '-') {
            x = true;
            if (!move()) throw new NumberFormatException();
        }
        int ans = 0;
        while (!isSpaceChar(buf[now])) {
            if (isHex(buf[now])) ans = ans * 16 + toHex(buf[now]);
            else throw new NumberFormatException();
            if (!move()) break;
        }
        return (x ? -1 : 1) * ans;
    }

    public char nextChar() throws IOException {
        if (!hasNext()) throw new NullPointerException();
        char tmp = buf[now];
        move();
        return tmp;
    }
    public int next(char[] s) throws IOException {
        if (!hasNext()) throw new NullPointerException();
        int len=0;
        while (!isSpaceChar(buf[now])&&len<s.length) {
            s[len++]=buf[now];
            if (!move()) break;
        }
        return len;
    }
    public boolean hasNext() throws IOException {
        return skip();
    }

    public boolean hasNextLine() throws IOException {
        return now < len || refill();
    }

    private boolean move() throws IOException {
        now++;
        return hasNextLine();
    }

    private boolean skip() throws IOException {
        if (!hasNextLine()) return false;
        while (isSpaceChar(buf[now])) {
            if (!move()) return false;
        }
        return true;
    }

    private boolean isSpaceChar(char c) {
        return !(c >= 33 && c <= 126);
    }

    private boolean isNum(char c) {
        return c >= '0' && c <= '9';
    }

    private boolean isHex(char c) {
        return c >= '0' && c <= '9' || c >= 'A' && c <= 'F';
    }

    private int toHex(char c) {
        if (c >= '0' && c <= '9') return c - '0';
        else return c - 'A' + 10;
    }

    private boolean refill() throws IOException {
        len = reader.read(buf);
        now = 0;
        return len > 0;
    }
}