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 \leq k \leq 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 \cdot k$ that satisfy the following condition: $1 \leq c \leq 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 \leq k < n \leq 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.

Difficulty: interview

Starter code:

Solutions:
n, k = list(map(int, input().split()))

t = list(map(int, input().split()))

d = [0 for _ in range(n)]

for _ in range(n):
  for i in range(n):
    if i % k != _ % k:
      d[_] += t[i]

print(max(abs(d[_]) for _ in range(n)))


n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
ans = -100000000
for i in range(k):
    cnt = 0
    for j in range(n):
        if j%k != i:
            cnt += a[j]
    ans = max(ans,abs(cnt))
print(ans)            


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
for b in range(n):
    closed = [b + i * k for i in range(-n, n)]
    closed = set(c for c in closed if 0 <= c < n)
    test = sum(a[i] == -1 and i not in closed for i in range(n))
    play = sum(a[i] == 1 and i not in closed for i in range(n))
    ans = max(ans, abs(test - play))

print(ans)


# = list(map(int, input().split()))
# = map(int, input().split())
n, k = list(map(int, input().split()))
z = list(map(int, input().split()))
ans = -1
for b in range(n):
    tans = 0
    for s in range(n):
        if (s - b) % k != 0:
            tans += z[s]
    if abs(tans) > ans:
        ans = abs(tans)
print(ans)


n, k = list(map(int, input().split()))
arr = [int(x) for x in input().split()]

def calculate(a):
    nonlocal arr
    e, s = 0, 0
    for i in range(a, n, k):
        if arr[i] == -1:
            e += 1
        else:
            s += 1
    e -= arr.count(-1)
    s -= arr.count(1)
    return abs(e - s)

l = []
for i in range(k):
    l.append(calculate(i))
print(max(l))


n, k = list(map(int, input().split()))
l = list(map(int, input().split()))
mx = 0
for b in range(n):
    s = []
    for i in range(n):
        if abs(b - i) % k:
            s.append(l[i])
    mx = max(mx, abs(sum(s)))
print(mx)


#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, K = getIntList()
#print(N)
za = getIntList()
rr = 0
for b  in range(K):
    r = 0
    for i in range(N):
        if i%K==b: continue
        r+= za[i]
    r = abs(r)

    rr = max(r,rr)

print(rr)




n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
answer = 0
for i in range(k):
    B = A.copy()
    C = []
    for j in range(n):
        if j % k != i:
            C.append(B[j])
    a = C.count(1)
    b = C.count(-1)
    if abs(a - b) > answer:
        answer = abs(a - b)
print(answer)


n, k = [int(v) for v in input().split()]
signs = [int(v) for v in input().split()]

tot_e = signs.count(1)
tot_s = signs.count(-1)

ans = 0

for b in range(k):
    me, ms = 0, 0
    for c in range(b, n, k):
        if signs[c] == 1:
            me += 1
        else:
            ms += 1
    ans = max(ans, abs((tot_e - me) - (tot_s - ms)))

print(ans)


n, k = map(int, input().split())
a = list(map(int, input().split()))
t = 0
s = 0
for i in range(n):
    if a[i] == 1:
        t += 1
    else:
        s += 1

num = 0
for i in range(k):
    t1, s1 = t, s
    for j in range(i, n, k):
        if a[j] == 1:
            t1 -= 1
        else:
            s1 -= 1

    num = max(num, abs(s1 - t1))

print(num)

def f(k, c):
    e = s = 0
    for i in range(n):
        if (i-c)%k != 0:
            if a[i] == 1: 
                e += 1
            else:
                s += 1
    #print(k, c, e,s)
    return abs(e-s)

read = lambda: map(int, input().split())
n, k = read()
a = list(read())
mx = 0
for c in range(0, k):
    mx = max(mx, f(k,c))
print(mx)

n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
s=0
for b in range(k):
	ans=0
	
	for i in range(1,n+1):
		if (i-b)%k!=0:
			ans+=a[i-1]
	s=max(s,abs(ans))
print(s)


def main():
    buf = input()
    buflist = buf.split()
    n = int(buflist[0])
    k = int(buflist[1])
    buf = input()
    buflist = buf.split()
    tab = list(map(int, buflist))
    test_count = 0
    social_count = 0
    for i in range(n):
        if tab[i] == 1:
            test_count += 1
        else:
            social_count += 1
    max_diff = 0
    for i in range(k):
        test_remaining = test_count
        social_remaining = social_count
        for j in range(i, n, k):
            if tab[j] == 1:
                test_remaining -= 1
            else:
                social_remaining -= 1
        diff = abs(test_remaining - social_remaining)
        if diff > max_diff:
            max_diff = diff
    print(max_diff)

def __starting_point():
    main()

__starting_point()

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

c = [0 for i in range(k)]
s = sum(a)
for i in range(n):
    c[i % k] += a[i]

ans = -1
for i in c:
    ans = max(ans, abs(s - i))
print(ans)


from sys import stdin,stdout

I = stdin.readline
P = stdout.write

n,k = map(int,I().split())
arr = [int(x) for x in I().split()]

e = 0
s = 0
ans = 0
for i in arr:
    if(i == -1):
        s+=1
    else:e+=1

for i in range(0,k):
    ce = 0
    cs = 0
    for j in range(i,n,k):
        if(arr[j] == -1):
            cs+=1
        else:
            ce+=1
    x = e-ce
    y = s - cs
    if(abs(x-y)>ans):ans = abs(x-y)
print(ans)

n,k = [int(x) for x in input().split()]

L = [int(x) for x in input().split()]

test = 0
for i in L:
    if i == 1:
        test +=1
        
social = len(L)-test

best = 0

for i in range(0,k):
    tt = 0
    ts = 0
    j = 0
    while i+j*k < n:
        if L[i+j*k] == 1:
            tt += 1
        else:
            ts += 1
        j += 1
    best = max(abs(test-tt-social+ts),best)
print(best)

from operator import itemgetter
#int(input())
#map(int,input().split())
#[list(map(int,input().split())) for i in range(q)]
#print("YES" * ans + "NO" * (1-ans))
n,k = list(map(int,input().split()))
ar = list(map(int,input().split()))
e= 0
s = 0
ans = 0
for j in  range(k):
    e = 0
    s = 0
    for i in range(n):
        if i % k == j:
            continue
        if ar[i] == 1:
            e += 1
        else:
            s += 1
    ans = max(ans,abs(e-s))
print(ans)


n,k=map(int,input().split())
l=list(map(int,input().split()))
e,s=0,0
for i in l:
    if i == 1:
        e+=1
    else:
        s+=1
ans=0
for i in range(k):
    e1,s1=e,s
    for j in range(i,n,k):
        if l[j] ==1:
            e1-=1
        else:
            s1-=1
    ans=max(ans,abs(e1-s1))
print(ans)

n, k = map(int, input().split())
a = list(map(int, input().split()))
answ = 0
for b in range(n):
    sm = 0
    for i in range(n):
        if (i - b) % k:
            sm += a[i]
    answ = max(answ, abs(sm))
print(answ)

n, k = map(int, input().split())
mas = list(map(int, input().split()))
ans = 0
for b in range(k):
    m = 0
    for i in range(n):
        if i % k == b:
            continue
        m += mas[i]
    ans = max(ans, abs(m))
print(ans)

n, k = (int(x) for x in input().split())
tabs = [int(x) for x in input().split()]

#print(n, k, tabs)

mods = [sum(tabs[i::k]) for i in range(k)]

#print(mods)

summods = sum(mods)
ans = -1
for i in range(k):
	cand = abs(summods - mods[i])
	if cand > ans:
		ans = cand

print(ans)

import sys
from math import floor, ceil

input = sys.stdin.readline

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

totBad = 0
totGood = 0

for i in a:
    if i == -1:
        totBad += 1
    else:
        totGood += 1

ans = 0
for i in range(k):
    curBad = 0
    curGood = 0
    for j in range(i, n, k):
        if a[j] == -1:
            curBad += 1
        else:
            curGood += 1 
    ans = max(ans, abs((totBad - curBad) - (totGood - curGood)))

print(ans)


n, k = list(map(int, input().split()))
t = list(map(int, input().split()))
sume = 0
sums = 0
ans = None
for i in range(n):
    if t[i] == 1: sume += 1
    else: sums += 1
        
for b in range(k):
    tsume = sume
    tsums = sums
    for i in range(b, n, k):
        if t[i] == 1: tsume -= 1
        else: tsums -= 1
    if ans == None: ans = abs(tsums-tsume)
    else: ans = max(ans, abs(tsums-tsume))
print(ans)
    


n,k=list(map(int,input().split()))
A=list(map(int,input().split()))

ANS=0
for i in range(k):
    ex=0
    so=0
    for l in range(n):
        if l%k==i:
            continue
        if A[l]==1:
            ex+=1
        else:
            so+=1

    if ANS<abs(ex-so):
        ANS=abs(ex-so)

print(ANS)
    


n, k = map(int, input().split())
mass = list(map(int, input().split()))
e = mass.count(1)
s = mass.count(-1)
popq = float('-inf')
for b in range(0, k):
    e1=e
    s1=s
    for vkladki in range(b, n, k):
        if mass[vkladki] == 1:
            e1 -= 1
        else:
            s1 -= 1
    popq = max(popq, abs(e1-s1))
print(popq)