A. Roman and Browser

This morning, Roman woke up and opened the browser with nn opened tabs numbered from 11 to nn. 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 kk-th (2≤k≤n−12≤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 bb) and then close all tabs with numbers c=b+i⋅kc=b+i⋅k that satisfy the following condition: 1≤c≤n1≤c≤n and ii is an integer (it may be positive, negative or zero).

For example, if k=3k=3, n=14n=14 and Roman chooses b=8b=8, then he will close tabs with numbers 22, 55, 88, 1111 and 1414.

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

Input

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

The second line consists of nn integers, each of them equal either to 11 or to −1−1. The ii-th integer denotes the type of the ii-th tab: if it is equal to 11, this tab contains information for the test, and if it is equal to −1−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||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

题意：

-1 和 1 两种浏览器标签，输入总标签数目n和每次关闭标签的间隔k。

你可以选择一个起始位置b，从b开始，依次关闭b,b+k,b+2*k,b+3*k......i*k; (i*k<=n)

求剩余标签里两种标签数目的最大差的绝对值

 

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
 
int a[105];
 
int main()
{
	int n,m,i,j,k,Max=-inf,l=0,r=0,x,y;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]==-1)
			l++;
		else
			r++;
	}
	//cout<<l<<" "<<r<<endl;
	for(i=1;i<=m;i++)		// b 
	{
		x=0,y=0;
		for(j=i;j<=n;j+=m)	// bi
		{
			if(a[j]==-1)
				x++;
			else
				y++;
		}
		//cout<<x<<" "<<y<<endl;
		Max=max(Max,abs(l-x-r+y));
	}
	cout<<Max<<endl;
	return 0;
}