Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]
    a = [[[0] * 4 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                a[i][j][0] = 0
            else:
                if i == 0:
                    a[i][j][0] = 1
                else:
                    a[i][j][0] = a[i - 1][j][0] + 1
            if s[-i-1][j] == "#":
                a[-i-1][j][1] = 0
            else:
                if i == 0:
                    a[-i-1][j][1] = 1
                else:
                    a[-i-1][j][1] = a[-i][j][1] + 1
            if s[i][j] == "#":
                a[i][j][2] = 0
            else:
                if j == 0:
                    a[i][j][2] = 1
                else:
                    a[i][j][2] = a[i][j-1][2] + 1
            if s[i][-j-1] == "#":
                a[i][-j-1][3] = 0
            else:
                if j == 0:
                    a[i][-j-1][3] = 1
                else:
                    a[i][-j-1][3] = a[i][-j][3] + 1
    mn = 0
    for i in range(h):
        for j in range(w):
            mn = max(mn, sum(a[i][j]) - 3)
    print(mn)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    h, w = map(int, input().split())
    lst = []
    for i in range(h):
        lst.append(list(input()))

    R = [[0] * w for _ in range(h)]
    L = [[0] * w for _ in range(h)]
    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if lst[i][j] == '.':
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j - 1] + 1

    for i in range(h):
        for j in range(w - 1, -1, -1):
            if lst[i][j] == '.':
                if j == w - 1:
                    R[i][j] = 1
                else:
                    R[i][j] = R[i][j + 1] + 1

    for i in range(h):
        for j in range(w):
            if lst[i][j] == '.':
                if i == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i - 1][j] + 1

    for i in range(h - 1, -1, -1):
        for j in range(w):
            if lst[i][j] == '.':
                if i == h - 1:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i + 1][j] + 1

    ans = 0
    x = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, max(x[i]))
    print(ans)


if __name__ == '__main__':
    slove()
### BUGGY CODE ###

N=int(input())
A=[input() for i in range(N)]

for i in range(N):
  B=A[:]
  del B[i]
  print(max(B))


### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))

maxA=max(A)
countNumber=A.count(maxA)

for i in range(N):
  if A[i]<maxA:
    print(maxA)
  elif countNumber>1:
    print(maxA)
  else:
    B=A[:]
    del B[i]
    print(max(B))
### BUGGY CODE ###

import numpy as np

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = np.array([[0 for j in range(n)] for i in range(n)],dtype=np.uint32)
for (l,r) in rails:
    xlist[l-1,r-1]+=1

sumsumlist = np.cumsum(np.cumsum(xlist,axis=1),axis=0)


for (p,q) in qs:
    if p>1:
        ans = sumsumlist[q-1][q-1] - sumsumlist[q-1][p-2] - sumsumlist[p-2][q-1] + sumsumlist[p-2][p-2]
    elif p==1:
        ans = sumsumlist[q-1][q-1]

    print(ans)


### FIXED CODE ###

from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])


for (p,q) in qs:
    ans = 0
    for i in range(p-1,q):
        ans = ans+sumlist[i][q]-sumlist[i][p-1]
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
mod = 10**9+7
P = 0
Q = 0

for i in range(N-1):
    for j in range(i+1, N):
        P = A[i] % mod
        Q = A[j] % mod
        ans += P * Q
print(ans % mod)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
k = int((10**9 + 8)/2)
sum = 0
sum_1 = 0

for i in range(N):
    sum += A[i]
sum = (sum**2)%mod

for j in range(N):
    sum_1 += A[j]**2
sum_1 = (sum_1)%mod

ans = sum - sum_1
ans = (ans*k)%mod

print(ans)
### BUGGY CODE ###

def DP():
  n,m=map(int,input().split())
  dp=[0]*(m+2)

  for i in range(n):  #商品を一つずつ見ていく。
    w,v=(map(int,input().split()))
    for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
      dp[j]=max(dp[j-w]+v,dp[j])
  return max(dp)
print(DP())



### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

def main(A,B,N):
    K=len(B)
    R=min(N,K)
    for i in range(R):
        if A[i]>B[i]:
            return sum(B[:i]+A[i:])
    return sum(B[:R]+A[R:])

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
BC=[]
for m in range(M):
    b,c=map(int,input().split())
    BC.append([c,b])
BC.sort()
BC=BC[::-1]
B=[]
for bc in BC:
    B+=[bc[0]]*bc[1]
print(main(A,B,N))

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))

BC=[]
for m in range(M):
    b,c=map(int,input().split())
    BC.append([b,c])

A.sort()
BC.sort(key=lambda x:x[1],reverse=True)

D=[]
for [b,c] in BC:
    D+=[c]*b
    if len(D)>N:
        break

if len(D)<N:
    D+=[0]*(N-len(D))

AD=[max(A[i],D[i]) for i in range(N)]
 
print(sum(AD))
### BUGGY CODE ###

S = input()
M = []
for i in range(len(S)):
    M.append(S[i])
z = 0
ans = 0
while z == 0:
    for i in range(len(M)):
        if i == len(M) - 1:
            z = 1
            print(ans)
        elif M[i] == 'B' and M[i + 1] == 'W':
            ans += 1
            M[i] = 'W'
            M[i + 1] = 'B'
            break




### FIXED CODE ###

S = input()
ans = 0
x = 0
for i in range(len(S)):
    if S[i] == 'B':
        x += 1
    else:
        ans += x
print(ans)
### BUGGY CODE ###

n = int(input())
stack = []
for _ in range(n):
    stack.append(int(input()))

candidate = []
for i, v in enumerate(stack):
    for j in stack[:i]:
        candidate.append(v - j)
        candidate = [max(candidate)]

print(candidate[0])

### FIXED CODE ###

n = int(input())
stack = []
for _ in range(n):
    stack.append(int(input()))

maxv = -10**9
minv = stack[0]
for i in range(1, len(stack)):
    maxv = max(maxv, stack[i] - minv)
    minv = min(minv, stack[i])

print(maxv)
### BUGGY CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

UnionFind=UnionFind(n+1)
for a,b in AB:
    UnionFind.Unite(a,b)

A=UnionFind.group_members()
ans=0
for i in range(1,n+1):
    ans=max(ans,UnionFind.size(i))
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline


class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

UnionFind=UnionFind(n+1)
for a,b in AB:
    if UnionFind.isSameGroup(a,b) is False:
        UnionFind.Unite(a,b)

ans=0
for i in range(1,n+1):
    cnt=UnionFind.size(i)
    if ans<cnt:
        ans=cnt
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
print(len([x for x in set(A) if A.count(x)%2==1]))

### FIXED CODE ###

import collections as co
N = int(input())
A = [int(input()) for i in range(N)]
c = co.Counter(A)
count = 0
for a,b in c.most_common():
    if b%2==1:
        count += 1
print(count)
### BUGGY CODE ###

import copy
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [0 for m in range(M + 1)]
for n in range(N):
    f_ = copy.copy(f)
    for m in range(M + 1):
        if m >= W[n]:
            f_[m] = max(f[m], f[m - W[n]] + V[n])
    f = f_
print(f[M])


### FIXED CODE ###

N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [[0 for m in range(M + 1)] for n in range(N + 1)]
for n in range(N):
    for m in range(M + 1):
        if m < W[n]:
            f[n + 1][m] = f[n][m]
        else:
            f[n + 1][m] = max(f[n][m], f[n][m - W[n]] + V[n])
print(f[N][M])
### BUGGY CODE ###

n, m = map(int, input().split()) 

alist=[]

for i in range(n):
    a, b = map(int, input().split()) 
    alist.append([a,b])

alist=sorted(alist)
#print(alist)

eternal=1
now=0
hoshu=0

koholist=[]
for i in range(m):
    j=i+1
    switch=1
    while switch==1 and eternal==1:
        if alist[now][0]<=j:
            koholist.append(alist[now][1])
            if now>=n-1:
                switch=0
                eternal=0
            else:
                now+=1
        else:
            switch=0
    if len(koholist)>0:
        saidai=max(koholist)
        koholist.remove(saidai)
        #print(saidai)
        hoshu+=saidai

print(hoshu)

### FIXED CODE ###

import heapq

n, m = map(int, input().split()) 

alist=[]

for i in range(n):
    a, b = map(int, input().split()) 
    alist.append([a,b])

alist=sorted(alist)
#print(alist)

eternal=1
now=0
hoshu=0

koholist=[]
for i in range(m):
    j=i+1
    switch=1
    while switch==1 and eternal==1:
        if alist[now][0]<=j:
            heapq.heappush(koholist, -alist[now][1])
            if now>=n-1:
                switch=0
                eternal=0
            else:
                now+=1
        else:
            switch=0
    if len(koholist)>0:
        saidai=heapq.heappop(koholist)
        #print(saidai)
        hoshu+=saidai

print(-hoshu)
### BUGGY CODE ###

def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0] * (N + 1)

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i
    bit = [0] * (N + 1)

    for i, a in enumerate(C, start=1):
        if i <= Query[0][0][1]:
            lastappend[a] = i
    for la in lastappend[1:]:
        if la != 0:
            add(bit, la, 1)
    pre = Query[0][0][1]
    ans = []
    for (le, ri), j in Query:
        if pre < N and pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    add(bit, pre_i, -1)
                lastappend[C[i-1]] = i
                add(bit, i, 1)
            pre = ri
        ans.append((j, sum(bit, ri) - sum(bit, le-1)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

SHIFT = 1 << 20


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = []
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query.append(ri << 40 | le << 20 | j)
    Query.sort()

    # Query復元
    for i in range(Q):
        j = Query[i] % (SHIFT)
        Query[i] >>= 20
        le = Query[i] % (SHIFT)
        Query[i] >>= 20
        ri = Query[i]
        Query[i] = (le, ri, j)
    Query.append((-1, -1, -1))

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i

    lastappend = [-1] * (N + 1)
    bit = [0] * (N + 1)
    idx = 0  # Queryのindex
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            add(bit, lastappend[a], -1)
        lastappend[a] = i
        add(bit, i, 1)
        while i == Query[idx][1]:
            (le, ri, j) = Query[idx]
            ans[j] = sum(bit, ri) - sum(bit, le-1)
            idx += 1

    print(*ans, sep="\n")


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
a = []
h = []
for i in range(n):
    arr= list(map(int,input().split()))
    h.append(arr[2])
    a.append(arr)


for i in range(101):
    for j in range(101):
        for k in range(min(h),min(h)+201):
            if all(max(k-abs(l[0]-i)-abs(l[1]-j),0) == l[2] for l in a):
                print(i,j,k)
                exit()

### FIXED CODE ###

n = int(input())
a = []
h = []
for i in range(n):
    arr= list(map(int,input().split()))
    h.append(arr[2])
    a.append(arr)
l = [i for i in a if i[2]>0]
xt = l[0][0]
yt = l[0][1]
ht = l[0][2] 
for i in range(101):
    for j in range(101):
        h_ans = ht+abs(xt-i)+abs(yt-j)    
        if all(max(h_ans-abs(l[0]-i)-abs(l[1]-j),0) == l[2] for l in a):
            print(i,j,h_ans)
            exit()
### BUGGY CODE ###

from sys import exit

N, Q = map(int, input().split())

S = input()

AC = []
for i in range(len(S) - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        AC.append(i)

ans = []

for i in range(Q):
    li, ri = map(int, input().split())

    count = 0
    for ac in AC:
        if ac < li - 1 or ri - 1 < ac + 1:
            count += 1
    ans.append(len(AC) - count)

for a in ans:
    print(a)


### FIXED CODE ###

from sys import exit

N, Q = map(int, input().split())

S = input()

AC = [0] * N

c = 0

for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    AC[i + 1] = c

for _ in range(Q):
    li, ri = map(int, input().split())
    print(AC[ri - 1] - AC[li - 1])
### BUGGY CODE ###

import itertools
n = int(input())

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

cs = list(itertools.combinations(ls,3))

count = 0
for c in cs:
    d = list(c)
    d.sort()
    if d[2] < d[0] + d[1]:
        count += 1
    

print(count)


### FIXED CODE ###

import bisect
n = int(input())

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

ls.sort()
count = 0
for i in range(n):
    for j in range(i + 1,n):
        t = ls[i] + ls[j]
        index = bisect.bisect_left(ls,t)
        count += max(0,index - j - 1)

print(count)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = lambda x: x[0] + x[1])
INF = 1<<64

dp = [0]
for i in range(N):
    hi, pi = HP[i]
    dp += [INF]
    for j in range(i+1, 0, -1):
        if dp[j-1] > hi:
            continue
        dp[j] = min(dp[j], dp[j-1]+pi)
for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)



### FIXED CODE ###

import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = lambda x: x[0] + x[1])
INF = 1<<64

dp = [0]
for i in range(N):
    hi, pi = HP[i]
    dp += [INF]
    for j in range(i+1, 0, -1):
        if dp[j-1] > hi:
            continue
        dp[j] = min(dp[j], dp[j-1]+pi)
for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)
### BUGGY CODE ###


from copy import deepcopy

def solve():
    N = int(raw_input())
    s = [int(_) for _ in raw_input().split()]
    ans = 0
    for A in range(1, N - 1):
        for B in range(1, A):
            if (N - 1) % (A - B) != 0 and (N - 1 - A) % (A - B) != 0:
                continue
            tmp_sum = 0
            pos = 0
            cnt = 0
            succ = True
            tmp_s = deepcopy(s)
            while pos < N - 1:
                if tmp_s[pos] is None:
                    succ = False
                    break
                else:
                    tmp_sum += tmp_s[pos]
                    tmp_s[pos] = None
                if cnt % 2 == 0:
                    pos += A
                else:
                    pos -= B
                cnt += 1
            if succ and pos == (N - 1):
                ans = max(ans, tmp_sum)
    print ans

if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve2():
    N = int(raw_input())
    s = [int(_) for _ in raw_input().split()]
    ans = 0
    pass_set = set()
    for C in range(1, N - 1):
        pass_set.clear()
        maxK = (N - 1) / C
        score = 0 # when k = 0: 0 -> (N - 1)
        for k in range(1, maxK+1):
            if N - 1 - k*C < C:
                break
            if (N-1-k*C) in pass_set or k*C in pass_set or (N-1-k*C) == k*C:
                break
            else:
                score += s[N-1-k*C] + s[k*C] # DP
                pass_set.add(N-1-k*C)
                pass_set.add(k*C)
            ans = max(ans, score)
    print ans

if __name__ == '__main__':
    solve2()
### BUGGY CODE ###

import math as m

a, b, x = map(int, input().split())

x = float(x)
d_max = float(90)
d_min = float(0)
res = float(100)

if x >= a**2*b:
    print(0)
    exit()

if x < a*a*b/100:
    d_max = float(1)

while res > 10e-8:
    d_mid = (d_max+d_min)/2
    l1 = a*m.tan(d_mid/180*m.pi)
    if l1-b > 0:
        l2 = (l1-b)*m.tan((90-d_mid)/180*m.pi)
    else:
        l2 = 0
    v = a*(a*b - 1/2*a*l1 + 1/2*(l1-b)*l2)
    res = abs(x-v)
    if x - v < 0:
        d_min = d_mid
    else:
        d_max = d_mid
print(d_mid)

### FIXED CODE ###

import math as m

def vol(a,b,x,d):
    if a**2*b / 2 < x:
        return a**2*b - 1/2*a**3 * m.tan(m.radians(d))
    else:
        return 1/2*a*b**2 * m.tan(m.radians(90-d))

a, b, x = map(int, input().split())

if a**2*b == x:
    print(0)
    exit()

res = x
d_max = 90
d_min = 0
while res > 10e-8:
    d = (d_max+d_min)/2
    if vol(a,b,x,d) - x > 0:
        d_min = d
    else:
        d_max = d
    res = abs(x - vol(a,b,x,d))

print(d)
### BUGGY CODE ###

import numpy as np
import sys


def DP(i, X, w, v):
    global memo
    if (X < 0):
        return -10 ** 9
    if (memo[i, X] != -10 ** 9):
        return memo[i, X]
    result = max(DP(i + 1, X, w, v),
                 DP(i + 1, X - w[i], w, v) + v[i])
    memo[i, X] = result
    return result


input = sys.stdin.readline
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
MINUS_INF = -10 ** 9
memo = np.full((N + 1, W + 1), MINUS_INF, dtype=np.int64)
memo[N, :] = 0
answer = DP(0, W, w, v)
print(answer)


### FIXED CODE ###

import numpy as np
import sys


def main():
    input = sys.stdin.readline
    n, W = map(int, input().split())
    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())
    ndp = np.zeros(W + 1, dtype=np.int64)
    for w, v in zip(w, v):
        np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])
    print(ndp[-1])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

if __name__ == '__main__':

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

    INF = 10**9
    dp = [INF] * (n+1)
    dp[0] = 0
    k = min(k,n)
    for i in range(1,n):
        for j in range(1,k+1):
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
    print(dp[n-1])



### FIXED CODE ###

if __name__ == '__main__':

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

    #TLE pypy
    INF = 10**9
    dp = [INF] * (n+1)
    dp[0] = 0
    k = min(k,n)
    for i in range(1,n):
        for j in range(1,k+1):
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
    print(dp[n-1])
### BUGGY CODE ###

s=[int(x) for x in input()]
from collections import deque
L=deque()
sum=0
for i in range(len(s)):
    t=s[i]*(10**(len(s)-i))
    sum += t
    L.append(sum%2019)
L=sorted(L)

ans=0
count=1
for i in range(len(L)-1):
    if L[i]==L[i+1]:
        count += 1
    else:
        if L[i]==0:
            count += 1
        if count>1:
            ans += count*(count-1)//2
        count=1
if count>1:
    ans += count*(count-1)//2

print(ans)


### FIXED CODE ###

from collections import deque
s=input()[::-1]
l=[0]*2019
ten=1
sm=0
cnt=0
l[0]=1
for i in range(len(s)):
    sm += int(s[i])*ten
    sm %= 2019
    cnt += l[sm]
    l[sm] += 1
    ten = ten *10 %2019
print(cnt)
### BUGGY CODE ###

from itertools import product as pd
f=lambda x,y:(x,y) if x<y else (y,x) 
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,c) in pd(range(n),repeat=2):
  for (b,d) in pd(range(n),repeat=2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=sum(1 for i in range(n) if lx<=o[i][0]<=rx and dy<=o[i][1]<=uy)
    if cnt==k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)

### FIXED CODE ###

from itertools import combinations as comb
n,k=map(int,input().split())
f=lambda x,y:(min(x,y),max(x,y))
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b) in comb(range(n),2):
  for (c,d) in comb(range(n),2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [-1 for _ in range(n)]
dp[0] = 0
for i in range(1,n):
    for j in range(1,k+1):
        if i - j < 0:
            break
        if dp[i] == -1:
            dp[i] = dp[i-j] + abs(h[i]-h[i-j])
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))
print(dp[n-1])


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = list(map(int, input().split()))
h = np.array(h)
dp =np.zeros(n, dtype='int64')
dp[0] = 0
for i in range(1,n):
    lo = max(i-k,0)
    dp[i] = np.min(dp[lo:i]+np.abs(h[i]-h[lo:i]))
print(dp[n-1])