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

import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]
    
    Q = int(input())

    mem = [[None for i in range(W*H + 1)] for i in range(W*H + 1)]

    for i in range(Q):
        l, r = map(int, input().split())
        if mem[l][r] != None:
            print(mem[l][r])
        else:
            ans = 0
            for t in range(l, r, D):
                ans += abs(hw[t][0] - hw[t+D][0]) + abs(hw[t][1] - hw[t+D][1])
            print(ans)
            mem[l][r]

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    # 各数字の座標をhw[]に格納
    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]

    # for i in range(len(hw)):
    #     print(i, hw[i])
    
    # Dのmodごとにmod Dからの距離を計算(累積和)
    modd = [0] * (H*W + 1)
    for start in range(D):
        tmp = start + D
        cost = 0
        if tmp == D:
            tmp = D * 2
        while tmp <= (H*W):
            tmp_cost = abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1])
            # print("{} - {} : {}".format(tmp-D, tmp, tmp_cost))
            # print(hw[tmp-D], hw[tmp], abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1]))
            cost += tmp_cost
            modd[tmp] = cost
            tmp += D
    # print(modd)
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(modd[r] - modd[l])

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush, heapify 
def main():
    N, M = map(int, readline().split())
    A = [int(i) for i in readline().split()]
    heapify(A)
    for _ in range(M):
        b, c = map(int, readline().split())
        for i in range(b):
            v = heappop(A)
            if v>=c:
                heappush(A, v)
                break
            else:
                heappush(A, c)
    print(sum(A))     
if __name__ == '__main__':
    main()


### FIXED CODE ###

#python3
from heapq import heappop, heappush

def main():
    n, m = map(int, input().split())
    hq = [] 
    for i in input().split():
        heappush(hq, (-int(i), 1))
    for _ in range(m):
        b, c = map(int, input().split())
        heappush(hq, (-c, b))
    ans = 0
    for i in range(n):
        v, u = heappop(hq)
        u = u - 1
        if u >= 1:
            heappush(hq, (v, u))
        v = - v 
        ans = ans + v
    print(ans)
main()
### BUGGY CODE ###

import sys
import math
# num = []
# for e in sys.stdin:
#     num.append(map(int, e.split()))

N = int(input())


for n in range(1, N+1):
    count = 0;
    max = min(int(math.sqrt(n)), int(n/2))
    for i in range(1, max+1):
        for j in range(1, max+1):
            for k in range(1, max+1):
                num = i**2 + j**2 + k**2 + i*j + j*k + k*i
                if n == num:
                    count+=1
    print(count)

### FIXED CODE ###

import sys
import math
import itertools
# num = []
# for e in sys.stdin:
#     num.append(map(int, e.split()))

N = int(input())

count = []
for i in range(N):
    count.append(0)

max = min(int(math.sqrt(N)), int(N/2))
l = []

for i in range(1, max+1):
    l.append(i)

h = itertools.combinations_with_replacement(l, 3)

# print(h)
for i,j,k in h:
    n = (i+j+k)**2 - i*j - j*k - k*i
    # print(n)

    if(n <=N):
        if(i==j==k):
            count[n-1]+=1
        elif(i==j or j==k or i == k):
            count[n-1]+=3
        else:
            count[n-1]+=6


for c in count:
    print(c)

# for n in range(1, N+1):
#     count = 0;
#     max = min(int(math.sqrt(n)), int(n/2))
#     l = []
#
#     for i in range(1, max+1):
#         l.append(i)
#
#     h = list(itertools.combinations_with_replacement(l, 3))
#     for i,j,k in h:
#         if n == (i+j+k)**2 - i*j - j*k - k*i:
#             if(i==j==k):
#                 count+=1
#             elif(i==j or j==k or i == k):
#                 count+=3
#             else:
#                 count+=6

    # for i in range(1, max+1):
    #     for j in range(1, max+1):
    #         for k in range(1, max+1):
    #             num = i**2 + j**2 + k**2 + i*j + j*k + k*i
    #             if n == num:
    #                 count+=1
    # print(count)


    # print(max)


    # l = []
    #
    # for i in range(1, max+1):
    #     l.append(i)
    #
    # # h = itertools.combinations_with_replacement(l, 3)
    #
    # for i,j,k in h:
    #     if n == i**2 + j**2 + k**2 + i*j + j*k + k*i:
    #         if(i==j==k):
    #             count+=1
    #         elif(i==j or j==k or i == k):
    #             count+=3
    #         else:
    #             count+=6
    # print(count)
### BUGGY CODE ###

n = int(input())
for i in range(1,3501):
    for j in range(i, 3501):
        top = n*i*j
        bot = 4*i*j - n*(i+j)
        if bot > 0 and top >= bot and top%bot == 0:
            w = top//bot
            if w >= j:
                print(i, j, w)
                exit()

### FIXED CODE ###

n = int(input())
for i in range(1,3501):
    for j in range(i, 3501):
        top = n*i*j
        bot = 4*i*j - n*(i+j)
        if bot > 0 and top%bot == 0:
            w = top//bot
            if w > 0:
                print(i, j, w)
                exit()
### BUGGY CODE ###

# coding: utf-8
# hello worldと表示する
import sys
#import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
pairs=[LI() for i in range(n)]
def pair_revise(x,y,a,b):
    global p
    global q
    #print(x,y,a,b)
    for i in range(max(1,min(floor(x/a),floor(y/b))),max(ceil(x/a),ceil(y/b))+1):
        p,q=a*i,b*i
        if p>=x and q>=y:
            break
    return [p,q]
    #return [x*max(ceil(x/a),ceil(y/b)),y*max(ceil(x/a),ceil(y/b))]
    #for i in range(max(ceil(x/a),ceil(y/b)),):
u,v=pairs[0]
for i in range(n-1):
    u,v=pair_revise(u,v,pairs[i+1][0],pairs[i+1][1])
print(u+v)
    
    
        





### FIXED CODE ###

# coding: utf-8
# hello worldと表示する
import sys
#import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def ceil(x,y):
    return (-1)*((-x)//y)
    
n=I()
pairs=[LI() for i in range(n)]
x,y=1,1
for i in range(n):
    a=pairs[i][0]
    b=pairs[i][1]
    k=max(ceil(x,a),ceil(y,b))
    x,y=a*k,b*k
print(x+y)





'''def pair_revise(x,y,a,b):
    global p
    global q
    i=max(ceil(x/a),ceil(y/b))
    p,q=a*i,b*i
    return p,q
u,v=1,1
for i in range(n):
    u,v=pair_revise(u,v,pairs[i][0],pairs[i][1])
    print(u,v)
print(u+v)'''
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  a=9999999999999
  hh=h[i]
  for j in range(1,min(k+1,i+1)):
    a=min(a,dp[i-j]+abs(h[i-j]-hh))
  dp[i]=a
print(dp[n-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  kk=max(i-k,0)
  dp[i]=min(d+abs(hh-h[i])for d,hh in zip(dp[kk:i],h[kk:i]))
print(dp[n-1])
### BUGGY CODE ###

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

def gcd(a, b):
  if a > b:
    a, b = b, a
  while b % a:
    a, b = b % a, a
  return a

def primes(n):
  primes = [2, 3]
  cands = list(range(3, n, 2))
  while True:
    last_prime = primes[-1]
    cands = [cand for cand in cands if cand % primes[-1] != 0]
    if len(cands) == 0:
      break
    primes.append(cands.pop(0))
  return primes
  

def main():
  a, b = map(int, input().strip().split())
  g = gcd(a, b)
  ps = []
  for p in primes(int(g ** 0.5)):
    if g % p == 0:
      ps.append(p)
    while g % p == 0:
      g //= p
      
  if g != 1:
    ps.append(g)
    
  print(len(ps) + 1)

if __name__=='__main__':
  main()



### FIXED CODE ###

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

def gcd(a, b):
  if a > b:
    a, b = b, a
  while b % a:
    a, b = b % a, a
  return a

def main():
  a, b = map(int, input().strip().split())
  g = gcd(a, b)
  
  count = 0
  for p in range(2, int(g ** 0.5 + 1)):
    if g % p == 0:
      count += 1
    while g % p == 0:
      g //= p
      
  if g != 1:
    count += 1
    
  print(count + 1)

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

def sort_2(a,b):
    if b<a:
        c=a
        a=b
        b=c
    return [a,b]


def GCDbase(a,b):
    D=b//a
    if b==D*a:
        return a
    else:
        return GCD(b-a*D,a)
    
def GCD(a,b):
    ab=sort_2(a,b)
    return GCDbase(ab[0],ab[1])

K=int(input())
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        t=GCD(i,j)
        for l in range(1,K+1):

            sum+=GCD(t,l)
print(sum)

### FIXED CODE ###

import math
K=int(input())
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp=math.gcd(i,j)
        for l in range(1,K+1):
            sum+=math.gcd(tmp,l)
print(sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, X, Y = map(int, input().split())
dic = {key: 0 for key in range(1, N)}
for i in range(1, N+1):
    for j in range(1, N+1):
        if(i < j):
            key = min(abs(j - i), abs(X - i)+1+abs(j - Y),
                      abs(Y - i) + 1 + abs(j - X))
            dic[key] += 1
for ans in dic.values():
    print(ans)


### FIXED CODE ###


N, X, Y = map(int, input().split())
dic = {key: 0 for key in range(1, N)}
for i in range(1, N+1):
    for j in range(1, N+1):
        if(i < j):
            key = min(abs(j - i), abs(X - i)+1+abs(j - Y),
                      abs(Y - i) + 1 + abs(j - X))
            dic[key] += 1
for ans in dic.values():
    print(ans)
### BUGGY CODE ###

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

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

def main():
    S = input()
    T = input()
    ls = len(S)
    lt = len(T)

    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], dp[i][j]+ (S[i]==T[j]))
#    print(dp)
#    print(dp[ls][lt])

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

import numpy as np

def main():
    S = np.array(list(input()), dtype='unicode')
    T = np.array(list(input()), dtype='unicode')
    ls = len(S)
    lt = len(T)

    equal = S[:, None] == T[None,:]
#    print(eq)

    dp = np.zeros((ls + 1, lt + 1), dtype=int)

    for i in range(ls):
        dp[i + 1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
        dp[i + 1] = np.maximum.accumulate(dp[i + 1])

#    for i in range(ls):
#        for j in range(lt):
#            dp[i+1][j+1] = max(dp[i][j+1], dp[i][j]+ eq[i][j])
#            dp[i+1][j+1] = max(dp[i+1][j+1] , dp[i+1][j])

#    print(dp)

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

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

#B問題
R, G, B, N = map(int, input().split())

ans = 0
for r in range(0, N // R + 1):
    for g in range(0, N // G + 1):
        if (N - R*r - G*g) % B == 0 and (N - R*r - G*g)/B >=0:
            ans += 1
print(ans)            

### FIXED CODE ###

#B問題
import math
R, G, B, N = map(int, input().split())

ans = 0
if R == G == B == 1:
    print (int((N+2)*(N+1)/2))
else:
    for r in range(0, N // R + 1):
        for g in range(0, N // G + 1):
            if (N - R*r - G*g) % B == 0 and (N - R*r - G*g)/B >=0:
                ans += 1
    print(ans)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
lisA = [int(i) for i in input().split()]
#print(n, m)
#print(lisA)

lisA.sort()
half0 = lisA[n-1]
count = n-1
for i in range(m):
	if (count < 0):
		count = n-1
	if (lisA[count] < half0):
		lisA.sort()
		half0 = lisA[n-1]
		count = n-1
	lisA[count] /= 2
	count -= 1
answer = 0
for i in range(n):
	answer += int(lisA[i])
print(answer)

### FIXED CODE ###

n, m = list(map(int, input().split()))
lisA = [int(i) for i in input().split()]
#print(n, m)
#print(lisA)

lisA.sort(reverse=True)
half0 = lisA[0] // 2
count = 0
for i in range(m):
	if (count > n - 1):
		count = 0
	if (lisA[count] < half0):
		lisA.sort(reverse=True)
		half0 = lisA[0] // 2
		count = 0
	lisA[count] //= 2
	count += 1
print(sum(lisA))
### BUGGY CODE ###

S = int(input())
count = 0
l = [0]*2019
l[0] = 1

for i in range(1,len(str(S))+1):
   l[(S%10**i)%2019] += 1

for j in range(2019):
    if l[j] >= 2:
        count += l[j]*(l[j]-1)//2

print(count)


### FIXED CODE ###

S = input()
count = 0
l = [0]*2019
l[0] = 1
mod = 2019
tmp = 0

for i in range(1,len(S)+1):
    tmp = (tmp + int(S[len(S)-i])*pow(10,i-1,mod))%mod
    l[tmp] += 1
    

for j in range(2019):
    if l[j] >= 2:
        count += l[j]*(l[j]-1)//2

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

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
number=[0]*n
for i in range(n-1):
    number[a[i]-1]+=1
for i in range(n):
    print(number[i])
### BUGGY CODE ###

import sys
import heapq
from functools import lru_cache


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    K = 0
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    n = N // 3

    @lru_cache(maxsize=None)
    def diff(s):
        count = 0
        for i in range(N):
            if A[i] == B[(i + s) % N]:
                count += 1

        if count == 0:
            print("Yes")
            L = []
            for i in range(N):
                L.append(B[(i + s) %N])
            print(*L)
            exit()

        return count

    l = 0
    r = N - 1
    diff(l)
    diff(r)

    while r - l > 1:
        a = diff(l + (r - l) // 3)
        b = diff(l + 2 * (r - l) // 3)
        if a > b:
            l = l + (r - l) // 3
        else:
            r =l + 2 * (r - l) // 3

    print("No")


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import heapq
from functools import lru_cache


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    n = N // 3

    @lru_cache(maxsize=None)
    def diff(s):
        count = 0
        for i in range(N):
            if A[i] == B[(i + s) % N]:
                count += 1

        if count == 0:
            print("Yes")
            L = []
            for i in range(N):
                L.append(B[(i + s) %N])
            print(*L)
            exit()

        return count

    l = 0
    r = N - 1
    diff(l)
    diff(r)

    while r - l > 2:
        a = diff(l + (r - l) // 3)
        b = diff(l + 2 * (r - l) // 3)
        if a > b:
            l = l + (r - l) // 3
        else:
            r =l + 2 * (r - l) // 3
    diff((l+r)//2)

    print("No")


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

a = int (input ())
b = 2
number = b

while number % a != 0 or number % b != 0:
    number += 1

print (number)

### FIXED CODE ###

def main():
    a, b = 2, int(input())
    ta, tb = a, b
    if b == 0: print(0)
    while a%b != 0:
       a, b = b, a%b
    print(int((ta*tb)/b))
main()
### BUGGY CODE ###

n = int(input())
base = input().split()
x = []
for i in base:
    x.append(int(i))
x.sort(reverse = False)
for i in range(1,n):
    a = x.count(i)
    print(a)
    for s in range(a):
        del x[0]
print(0)

### FIXED CODE ###

import collections

n = int(input())
base = input().split()
x = []
for i in base:
    x.append(int(i))
#x.sort(reverse = False)
c = collections.Counter(x)
for i in range(1,n):
    print(c[i])
print(0)
### BUGGY CODE ###

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

a = [int(input()) for i in range(M)]

wa = (10**9) + 7

#dpを使う

dp = [0]*(N+1)
dp[0]=1
for i in range(1,N+1):
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i in a:
        dp[i]=0

print(dp[N]%wa)





### FIXED CODE ###

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

a = [int(input()) for i in range(M)]

wa = (10**9) + 7

#dpを使う

dp = [0]*(N+1)
dp[0]=1
now_a = 0
if len(a)==0:
    now_a = -1
if len(a)!=0:
    a.reverse()
    now_a = a.pop()

for i in range(1,N+1):
    # print(now_a)
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i == now_a:
        dp[i]=0
        if len(a)!=0:
            now_a = a.pop()
        else:
            now_a = -1

# print(dp)

print(dp[N]%wa)
### BUGGY CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i *= 10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)


### FIXED CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)
### BUGGY CODE ###

# coding: utf-8
X,Y,A,B,C=map(int,input().split())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))
R=list(map(int,input().split()))

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

EP=P[0:X]
EQ=Q[0:Y]

    # for i in range(X):
    #     EP.append(P[i])
        
    # for i in range(Y):
    #     EQ.append(Q[i])

EP.sort()
EQ.sort()

for i in range(C):
    if R[i]>EP[0] or R[i]>EQ[0]:
        if EP[0]<EQ[0]:
            EP.pop(0)
            EP.append(R[i])
        else:
            EQ.pop(0)
            EQ.append(R[i])
    else:
        break

print(sum(EP)+sum(EQ))




### FIXED CODE ###

# coding: utf-8
X,Y,A,B,C=map(int,input().split())
P=list(map(int,input().split()))
Q=list(map(int,input().split()))
R=list(map(int,input().split()))

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

EP=P[0:X]
EQ=Q[0:Y]

    # for i in range(X):
    #     EP.append(P[i])
        
    # for i in range(Y):
    #     EQ.append(Q[i])

EP.reverse()
EQ.reverse()

ans=sum(EP)+sum(EQ)

p=0
q=0

INF=10**12

EP.append(INF)
EQ.append(INF)

for i in range(C):
    if R[i]>EP[p] or R[i]>EQ[q]:
        if EP[p]<EQ[q]:
            ans+=R[i]
            ans-=EP[p]
            p+=1
        else:
            ans+=R[i]
            ans-=EQ[q]
            q+=1
    else:
        break

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

N,K = map(int,input().split())
max_total = 0
res = 0
p = list(map(int,input().split()))
for i in range(N-K+1):
  total = sum(p[i:i+K])
  if total >= max_total:
    max_total = total
    res_number = i
for j in range(res_number,res_number+K):
  res += (p[j]+1)/2
print(res)

### FIXED CODE ###

N,K = map(int,input().split())
max_total = 0
res = 0
p = list(map(int,input().split()))
for _ in range(len(p)):
  p[_] = (p[_]+1)/2
  
total = sum(p[0:K])
max_total = total
for i in range(K,N):
  if p[i] > p[i-K]:
    total = total + p[i] - p[i-K]
    max_total = max(max_total,total)
  else:
    total = total + p[i] - p[i-K]

print(max_total)