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

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float("inf") for _ in range(N)]

def cost(n, m):
  return abs(h[n] - h[m])

dp[0] = 0

for i in range(N):
  for j in range(1, K + 1):
    if (i + j) <= N -1:
      dp[i + j] = min(dp[i + j], dp[i] + cost(i, i + j))

print(dp[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float("inf") for _ in range(N)]

def cost(n, m):
  return abs(h[n] - h[m])

dp[0] = 0

for i in range(N):
  for j in range(1, K + 1):
    if (i + j) <= N -1:
      dp[i + j] = min(dp[i + j], dp[i] + cost(i, i + j))

print(dp[-1])
### BUGGY CODE ###

def f(L):
    n = len(L)
    L.sort()
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            a, b = L[i], L[j]
            for k in range(n):
                if k != i and k != j and L[k] < a + b:
                    # other two checks
                    if a < b + L[k] and b < L[k] + a:
                        count += 1
                else:
                    break
    return count

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)


### FIXED CODE ###

import bisect

def f(L):
    n = len(L)
    L.sort()

    count = 0

    for i in range(n):
        for j in range(i + 1, n):
            a = L[i]
            b = L[j]
            start = max(a - b, b - a)
            end = a + b
            si = bisect.bisect_right(L, start)
            ei = bisect.bisect_left(L, end)
            zx = ei - si
            if i >= si and i < ei:
                zx -= 1
            if j >= si and j < ei:
                zx -= 1
            count += zx
    return count // 3

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

cntli = []
for i in range(q):
    si = s[lr[i][0]-1:lr[i][1]]
    cnt = 0
    for j in range(len(si)-1):
        if si[j] == "A":
            if si[j+1] == "C":
                cnt += 1
    else:
        cntli.append(cnt)

for p in cntli:
    print(p)

### FIXED CODE ###

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

t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

N=int(input())
d=list(map(int, input().split()))
C=N//2
for x in reversed(range(1,N+1)):
    for y in range(0,x-1):
        if d[y]<d[y+1]:
            t=d[y]
            d[y]=d[y+1]
            d[y+1]=t
if d[C]==d[C-1]:
    print(0)
else:
    print(d[C-1]-d[C])


### FIXED CODE ###

N=int(input())
d=list(map(int, input().split()))
C=N//2
d.sort()
if d[C]==d[C-1]:
    print(0)
else:
    print(d[C]-d[C-1])
### BUGGY CODE ###

# import time
R, G, B, N = map(int, input().split())
# print(R, G, B)
i = 0
# r, g = 0, 0
# s = time.time()
for r in range(N // R + 1):
    for g in range(N // G + 1):
        if (N - r * R - g * G) >= 0:
            b = int((N - r * R - g * G) / B)
            if N - (r * R + g * G + b * B) == 0:
                # print(r, g, b)
                i += 1
print(i)
# print(time.time()-s)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
i = 0
for r in range(N // R + 1):
    Rr = r * R
    for g in range(N // G + 1):
        Gg = g * G
        Bb = N-Rr-Gg
        if Bb < 0:
            break
        if Bb % B == 0:
            i += 1
print(i)
### BUGGY CODE ###

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

result = 1
for i in A:
    result *= i

if result > 10**18:
    print(-1)
else:
    print(result)


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    result = 1
    if 0 in A:
        print(0)
        return

    for i in A:
        result *= i
        if result > 10**18:
            print(-1)
            return
    print(result)

main()
### BUGGY CODE ###

import itertools

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]

MOD = 10**9 + 7

B = 2**N
dp = [0]*B
dp[B-1] = 1

bit = [[] for _ in range(N+1)]
for v in list(itertools.product([0,1], repeat=N)):
    s = sum(v)
    b = int("".join(list(map(str, v))), 2)
    bit[s].append(b)

for not_matched_woman in reversed(range(1,N+1)):
    for b in bit[not_matched_woman]:
        for i in [i for i in range(N) if A[not_matched_woman-1][i]]:
            if b & (1 << i):
                dp[b ^ (1 << i)] += dp[b]
                dp[b ^ (1 << i)] %= MOD

print(dp[0])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7

memo = [-1] * 2**N
memo[0] = 1

def dfs(bit_state, matched):
    if memo[bit_state] != -1:
        return memo[bit_state]
    r = 0
    for i in range(N):
        if bit_state & (1 << i) and A[matched][i]: # bitでi桁目の女性未マッチング かつ 男性がi桁目の女性に対し相性OK
            r += dfs(bit_state ^ (1 << i), matched+1) # i桁目の女性をマッチング済にして遷移
    r %= MOD
    memo[bit_state] = r
    return r

print(dfs(2**N-1, 0))
### BUGGY CODE ###

from collections import Counter
import sys
def input() -> str:
    return sys.stdin.readline()
n = int(input())
s = [input() for _ in range(n)]
clist, cnt = [], []
for si in s:
    c = Counter(si)
    # print(c)
    if c in clist:
        cnt[clist.index(c)] += 1
    else:
        clist.append(c)
        cnt.append(1)
ans = 0
for ci in cnt:
    ans += sum(range(1, ci))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = ["".join(sorted(input().split()[0])) for _ in range(n)]
cnt = {}
result = 0
for si in s:
    if si in cnt:
        result += cnt[si]
        cnt[si] += 1
    else:
        cnt[si] = 1
print(result)
### BUGGY CODE ###

from collections import Counter


def check(s1, s2, i, j, memo):
    if memo[i] == memo[j] and memo[i] != -1:
        return 1
    elif memo[i] != memo[j] and memo[j] != -1:
        return 0

    s1_cnt = Counter(s1)
    s2_cnt = Counter(s2)

    if s1_cnt == s2_cnt:
        if memo[i] == -1:
            memo[i] = i
            memo[j] = i
        elif memo[j] == -1:
            memo[j] = memo[i]
        return 1

    else:
        return 0



def main():
    N = int(input())

    S = []
    for _ in range(N):
        S.append(input())

    ans = 0
    memo = [-1 for i in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            ans += check(S[i], S[j], i, j, memo)

    print(ans)


main()

### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
ans_dict = {}

for _ in range(n):
    s = list(input())
    s.sort()
    s = ''.join(s)
    try:
        ans_dict[s] += 1
    except:
        ans_dict[s] = 1

ans = 0
for key in ans_dict:
    if ans_dict[key] >= 2:
        ans += combinations_count(ans_dict[key], 2)
print(ans)
### BUGGY CODE ###


n=int(input())
a=list(map(int,input().split()))
s=0
for i in set(a):
    m=a.count(i)
    s+=m*(m-1)//2
for i in a:
    print(s-a.count(i)+1)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
s=0
m=Counter(a)
for i in m.values():
    s+=i*(i-1)//2
for i in a:
    print(s-m[i]+1)
### BUGGY CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
li = sorted(list_A)
if li[0] == li[-1]:
    print(N%(7+10**9))
else:
    for i in range(1, N):
        ans *= list_A[i] // fractions.gcd(ans, list_A[i])
    for a in list_A:
        sum += ans//a
    print(sum%(7+10**9))

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
for i in range(1, N):
  ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
  sum += ans//a
print(sum%(7+10**9))
### BUGGY CODE ###

import sys

def segfunc(x, y):
    return min(x, y)

class segment_():
    def __init__(self, init_val, n, segfunc):
        self.ide_ele = 10**9+1
        # num: n以上の最小の2のべき乗
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        self.segfunc = segfunc
        # set_val
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]
        # built
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, x = map(int,sys.stdin.readline().split())
    A = list(map(int,sys.stdin.readline().split()))

    seg_ = segment_(A, n, lambda a, b: min(a, b))
    ans = 10**19
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += seg_.query(i-k, i+1)
            else:
                t += min(seg_.query(0, i+1), seg_.query(n-(k-i), n))
        ans = min(t, ans)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
c=list(map(int,input().split()))
dp=[0]
if n>1:
    dp.append(abs(c[1]-c[0]))
    for i in range(2,n):
        m=10**9+1
        for j in range(1,k+1):
            if j<n:
                m=min(m,dp[max(0,i-j)]+abs(c[i]-c[max(0,i-j)]))
        dp.append(m)
print(dp[-1])


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int,input().split())))

d = [[a[i][0]-a[i][1],a[i][0]+a[i][1]] for i in range(n)]

d = sorted(d, key = lambda x: x[1])
#print(d)

b = [-100000000000000000]
c = [0]


for i in range(n):
    for j in range(len(b)):
        if d[i][0] >= b[j]:
            if d[i][1] in b:
                c[b.index(d[i][1])] = c[j] + 1
            else:
                b.append(d[i][1])
                c.append(c[j]+1)
    
#print(b)
#print(c)

print(max(c))
        
    


### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int,input().split())))

d = [[a[i][0]-a[i][1],a[i][0]+a[i][1]] for i in range(n)]

d = sorted(d, key = lambda x: x[1])
#print(d)

b = [-100000000000000000]
c = [0]


for i in range(n):
    for j in range(len(b)):
        if d[i][0] >= b[j]:
            b = [d[i][1]]
            c = [c[j] + 1]
            break

    
    #print(b)
    #print(c)

print(max(c))
### BUGGY CODE ###

A, B, K = list(map(int, input().strip().split(' ')))
for j in range(A,B+1):
    if not(j >= A+K and j <= B-K):
        print(j)

### FIXED CODE ###

A, B, K = list(map(int, input().strip().split(' ')))
for j in range(A,min(A+K,B+1)):
    if not(j >= A+K and j <= B-K):
        print(j)
for i in range(max(B-K,j+1),B+1):
    if not(i >= A+K and i <= B-K):
        print(i)
### BUGGY CODE ###

import numpy as np

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

points = np.array([K for n in range(N)])

for q in range(Q):
    A = int(input()) - 1
    points -= 1
    points[A] +=1

for n in range(N):
    if points[n] < 1:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

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

points = np.array([K - Q for _ in range(N)])

for q in range(Q):
    A = int(input()) - 1
    points[A] +=1

for p in points:
    if p < 1:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

from pprint import pprint
import heapq

def solve(n, a, b):
    b_pq = []
    b_rev = {}
    delete = []
    for i, b_i in enumerate(b):
        if b_i == a[i]:
            continue
        heapq.heappush(b_pq, (-1 * b_i, i))

    count = 0
    while b_pq:
        tmp = heapq.heappop(b_pq)
        # pprint(tmp)
        b_i = tmp[0] * -1
        i_b = tmp[1]
        # print(i_b, b_i)
        i_a = (i_b - 1 + n) % n
        i_c = (i_b + 1) % n
        b_cand = b_i
        if b_cand - b[i_a] - b[i_c] < a[i_b]:
            continue

        #while b_cand - b[i_a] - b[i_c] >= a[i_b]:
        #    b_cand = b_cand - b[i_a] - b[i_c]
        #    count += 1
        tmp_count =  (b_cand - a[i_b]) // (b[i_a] + b[i_c])
        b_cand -= (b[i_a] + b[i_c]) * tmp_count
        count += tmp_count

        b[i_b] = b_cand
        heapq.heappush(b_pq, (-1 * b_cand, i_b))
        # print("count: ", count)
        # pprint(b)
        if b_cand == a[i_b] and b == a:
            return count
    
    return -1


if __name__ == '__main__':

    n = int(input().strip())
    a = list(map(int, input().strip().split(" ")))
    b = list(map(int, input().strip().split(" ")))
    print(solve(n, a, b))

### FIXED CODE ###

from pprint import pprint
import heapq

def solve(n, a, b):
    b_pq = []
    b_rev = {}
    delete = []
    for i, b_i in enumerate(b):
        if b_i == a[i]:
            continue
        heapq.heappush(b_pq, (-1 * b_i, i))

    count = 0
    while b_pq:
        tmp = heapq.heappop(b_pq)
        # pprint(tmp)
        b_i = tmp[0] * -1
        i_b = tmp[1]
        # print(i_b, b_i)
        i_a = (i_b - 1 + n) % n
        i_c = (i_b + 1) % n
        b_cand = b_i
        if b_cand - b[i_a] - b[i_c] < a[i_b]:
            continue

        #while b_cand - b[i_a] - b[i_c] >= a[i_b]:
        #    b_cand = b_cand - b[i_a] - b[i_c]
        #    count += 1
        tmp_count =  (b_cand - a[i_b]) // (b[i_a] + b[i_c])
        b_cand -= (b[i_a] + b[i_c]) * tmp_count
        count += tmp_count

        b[i_b] = b_cand
        if b_cand != a[i_b]:
            heapq.heappush(b_pq, (-1 * b_cand, i_b))
        # print("count: ", count)
        # pprint(b)
         

        if b_cand == a[i_b] and b == a:
            return count
    
    return -1


if __name__ == '__main__':

    n = int(input().strip())
    a = list(map(int, input().strip().split(" ")))
    b = list(map(int, input().strip().split(" ")))
    print(solve(n, a, b))
### BUGGY CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))
def ma():return map(int,input().split())
from itertools import accumulate as acc
import operator as op
import copy as cp
import math 


cnt=0
n=ri()
lu=rli()
lu.sort()
if n<=2:
  print(0)
else:
  for i in range(n-2):
    for j in range(i+1,n-1):
      r=n
      l=j
      
      while r-l>1 :
        mid=(r+l)//2
        if lu[i]+lu[j]>lu[mid]:
          l=mid
        else:
          r=mid
      cnt+=l-j
  print(cnt)

### FIXED CODE ###

n=int(input())
l=sorted(map(int,input().split()))
from bisect import *
print(sum(bisect_left(l,l[i]+l[j])-i-1 for i in range(n) for j in range(i)))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=1
for i in l:
	ans=ans*i
if ans>pow(10,18):
	ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=1
z=pow(10,18)
for i in l:
	ans=ans*i
	if ans>z:
		ans=-1
		break
if 0 in l:
	print(0)
else:
	print(ans)
### BUGGY CODE ###

t = input()
ans = ""
for i in t:
    if i == "?":
        ans += "D"
    else:
        ans += i


print(ans)

### FIXED CODE ###

t = input()

print(t.replace("?", "D"))
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = {}
for i in range(N):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
def move2next(now,move_cnt):
    state = move_cnt % 3
    if used[now][state] == mod:
        used[now][state] = move_cnt
        for route in routes[now]:
            move2next(route,move_cnt+1)
    # if used[now, state] <= move_cnt:
    #     flag = False # この条件だと前より遅いので探索ストップ
    # else:
    #     used[now, state] = move_cnt
    #     for route in routes[now]:
    #         move2next(route, move_cnt+1)


q = queue.Queue()
q.put((S,0))
# Deep First Serch
while q.empty() == False:
    now, cost = q.get()
    state = cost % 3
    if used[now,state] == mod:
        used[now,state] = cost
        for route in routes[now]:
            q.put((route,cost+1))

# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque

# q = queue.Queue()
q = deque()
q.append((S,0))
# Deep First Serch
while q:
    now, cost = q.popleft()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.append((route,cost+1))


# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(m)]

for b,c in BC:
  A.sort()
  idx=bisect.bisect_left(A,c)
  for i in range(min(b,idx)):
    A[i]=c
print(sum(A))

### FIXED CODE ###

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

BC.sort(key=lambda x:(x[1],x[0]),reverse=True)
cnt=0
for b,c in BC:
  for _ in range(b):
    if cnt>=n: break
    A.append(c)
    cnt+=1
A.sort(reverse=True)
print(sum(A[:n]))
### BUGGY CODE ###

#from collections import deque
#import sys
#sys.setrecursionlimit(10**6)
#input = sys.stdin.buffer.readline
n,m=map(int,input().split())
g = [[] for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = [(0,-1)]
d=[-1]*n
d[0]=0
res={}
while len(q)>0:
    u,r = q.pop(0)
    for v in g[u]:
        if d[v] == -1 and r != v:
            d[v] = d[u] + 1
            q.append((v,u))
            if not v-1 in res:
                res[v-1] = u+1
res = sorted(res.items())
if len(res) != n-1:
    print("No")
    exit()
print("Yes")
for i,j in res:
    print(j)

### FIXED CODE ###

from collections import deque
#import sys
#sys.setrecursionlimit(10**6)
#input = sys.stdin.buffer.readline
n,m=map(int,input().split())
g = [[] for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
q = deque([(0,-1)])
d=[-1]*n
d[0]=0
res={}
while len(q)>0:
    u,r = q.popleft()
    for v in g[u]:
        if d[v] == -1 and r != v:
            d[v] = d[u] + 1
            q.append((v,u))
            if not v-1 in res:
                res[v-1] = u+1
res = sorted(res.items())
if len(res) != n-1:
    print("No")
    exit()
print("Yes")
for i,j in res:
    print(j)
### BUGGY CODE ###

def binarySearch(key, lst):
    while len(lst) >= 1:
        i = len(lst) / 2
        if lst[i] > key:
            lst = lst[:i]
        elif lst[i] < key:
            lst = lst[i + 1:]
        else:
            return True
    return False

if __name__ == "__main__":
    input()
    S = map(int, raw_input().split())
    input()
    T = map(int, raw_input().split())

    n = 0
    for t in T:
        if binarySearch(t, S[:]):
            n += 1
    print n

### FIXED CODE ###

def binarySearch(key, lst):
    start = 0
    end = len(lst) - 1
    while end - start >= 0:
        i = (end - start) / 2 + start
        if lst[i] > key:
            end = i - 1
        elif lst[i] < key:
            start = i + 1
        else:
            del lst[i]
            return True
    return False

if __name__ == "__main__":
    input()
    S = map(int, raw_input().split())
    input()
    T = map(int, raw_input().split())

    n = 0
    for t in T:
        if binarySearch(t, S):
            n += 1
    print n
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math

N, K = map(int, input().split())
P = list(map(int, input().split()))

def expected(x):
    s = 0
    if x % 2 == 1:
        s = x * math.ceil(x / 2)
    else:
        s = (x + 1) * (x / 2)

    return s / x

b = {}
mx = 0

for i in range(N - K + 1):
    s = 0
    for j in range(K):
        k = i + j
        if not P[k] in b:
            b[P[k]] = expected(P[k])
        s += b[P[k]]
    mx = max(mx, s)

print(mx)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
from collections import deque

N, K = map(int, input().split())
P = list(map(int, input().split()))

def expected(x):
    s = 0
    if x % 2 == 1:
        s = x * math.ceil(x / 2)
    else:
        s = (x + 1) * (x / 2)

    return s / x

b = {}
mx = 0
# 前回分
q = deque()
p = 0

for i in range(N - K + 1):
    s = 0
    # 初回は全部計算
    if i == 0:
        for j in range(K):
            k = i + j
            if not P[k] in b:
                b[P[k]] = expected(P[k])
            s += b[P[k]]
            # 順番に保持
            q.append(b[P[k]])
    else:
        # 追加分
        k = i + (K - 1)
        if not P[k] in b:
            b[P[k]] = expected(P[k])
        # シフト
        f = q.popleft()
        q.append(b[P[k]])

        # 計算
        s = p - f + b[P[k]]

    # 最大更新
    mx = max(mx, s)
    # 前回分として保持
    p = s

print(mx)