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

def main():
    N, K = map(int, input().split())
    X = []
    Y = []
    XY = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
        XY.append((x, y))
    X.sort()
    Y.sort()
    ans = float('INF')
    for l in range(N):
        for r in range(N):
            for t in range(N):
                for d in range(N):
                    lx = X[l]
                    rx = X[r]
                    ty = Y[t]
                    dy = Y[d]
                    c = 0
                    for x, y in XY:
                        if lx <= x <= rx and dy <= y <= ty:
                            c += 1
                    if c >= K:
                        ans = min(ans, abs(rx - lx) * abs(ty - dy))
    print(ans)


main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    X = []
    Y = []
    XY = []
    for _ in range(N):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
        XY.append((x, y))
    X.sort()
    Y.sort()

    ans = float('INF')
    for l in range(N):
        for r in range(l + 1, N):
            for d in range(N):
                for t in range(d + 1, N):
                    lx = X[l]
                    rx = X[r]
                    ty = Y[t]
                    dy = Y[d]
                    c = 0
                    for x, y in XY:
                        if lx <= x <= rx and dy <= y <= ty:
                            c += 1
                    if c >= K:
                        ans = min(ans, abs(rx - lx) * abs(ty - dy))
    print(ans)


main()
### BUGGY CODE ###

# ABC 163
N =int(input())
A =[int(j) for j in input().split()]
for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

# ABC 163
N =int(input())
A =[int(j) for j in input().split()]
memo = [0] * N

for a in A:
    memo[a -1]+=1
for i in memo:
    print(i)
### BUGGY CODE ###

import math
A, B, N = map(int, input().split())

l = []
for x in range(N+1):
    l.append(math.floor(A*x/B) - A*math.floor(x/B))

print(max(l))


### FIXED CODE ###

import math
A, B, N = map(int, input().split())

x = min(B-1, N)
print(math.floor(A*x/B) - A*math.floor(x/B))
### BUGGY CODE ###

from fractions import gcd

Mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

lm = A[0]
for i in range(1,N):
    lm = lm*A[i] // gcd(lm,A[i])

ans = 0
for i in range(N):
    ans += ( lm//A[i] )
    ans %= Mod

print(ans)

### FIXED CODE ###

from fractions import gcd

Mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

lm = A[0]
for a in A[1:]:
    lm = lm*a//gcd(lm,a)

ans = 0
for i in range(N):
    ans += lm//A[i]
ans %= Mod

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

N = int(input())
def solve(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return solve(n-1)+solve(n-2)
print(solve(N))

### FIXED CODE ###

N = int(input())
dp = [0]*(N+1)
dp[0] = 2
dp[1] = 1
for i in range(2,N+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N])
### BUGGY CODE ###

# A - Integer Product 
from decimal import Decimal

n = int(input())
a = [input() for _ in range(n)]

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  bi = Decimal(a[i])*(10**9)
  c = 0
  while(bi%2 == 0 and c < 18):
    c += 1
    bi //= 2
  p2[i] = c
  c = 0
  while(bi%5 == 0 and c < 18):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(20)] for _ in range(20)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(18,-1,-1):
  for j in range(18,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[18-p2[i]][18-p5[i]]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)

### FIXED CODE ###

# A - Integer Product 
n = int(input())
a = [input() for _ in range(n)]

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  if '.' in a[i]:
    bi = int(a[i].replace('.','')+'0'*(9-(len(a[i])-a[i].index('.')-1)))
  else:
    bi = int(a[i])*(10**9)
  c = 0
  while(bi%2 == 0 and c < 18):
    c += 1
    bi //= 2
  p2[i] = c
  c = 0
  while(bi%5 == 0 and c < 18):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(20)] for _ in range(20)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(18,-1,-1):
  for j in range(18,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[18-p2[i]][18-p5[i]]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)
### BUGGY CODE ###

def main():
    s = input().rstrip()
    s = s[::-1]
    s += "0"
    n = len(s)
    a = [int(c) for c in s]
    dp = [[float("inf")]*2 for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = a[i] + j
            for num in range(10):
                ni = i+1
                nj = 0
                rem = num - x
                if rem < 0:
                    nj = 1
                    rem += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num + rem)
    print(dp[n][0])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input().rstrip()
    s = "0" + s
    dp = [0, float("inf")]
    for c in s:
        x = int(c)
        dp = [min(dp[0] + x, dp[1] + (10-x)), min(dp[0] + x+1, dp[1] + (10-x) - 1)]
    print(dp[0])

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

from functools import lru_cache

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")

box = [0] * (maxbit + 1)

@lru_cache(maxsize=None)
def f(i):
  cnt = 0
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

for i in range(1, maxbit + 1):
  box[i] = f(i)

for i in range(lenx):
  if x[i] == "0":
    mb = maxbit + 1
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    mb = maxbit - 1
    t = x10 - 2 ** (lenx - 1 - i)
  # print(t, mb)
  if t == 0:
    print(0)
  else:
    t %= mb 
    if t == 0:
      print(1)
    else:
      ans = f(t) + 1 
      box[t] = ans
      print(ans)

### FIXED CODE ###

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")
xc0 = x10 % (maxbit + 1)
xc1 = x10 % (maxbit - 1) if maxbit > 1 else 0

def f(ii):
  cnt = 0
  while ii > 0:
    ii %= bin(ii).count("1")
    cnt += 1
  return cnt

for i in range(lenx):
  if x[i] == "0":
    t = xc0 + pow(2, (lenx - 1 - i), maxbit + 1)
    ans = f(t % (maxbit + 1)) + 1
  else:
    if maxbit - 1 == 0:
      ans = 0
    else:
      t = xc1 - pow(2, (lenx - 1 - i), maxbit - 1)
      ans = f(t % (maxbit - 1)) + 1
  print(ans)
### BUGGY CODE ###

N=int(input())
A= [int(i) for i in input().split()]
import copy
for i in range(N):
    B=copy.deepcopy(A)
    B.pop(i)
    dist=0
    dist=dist+abs(B[0])
    for j in range(1,N-1):
        dist=dist+abs(B[j-1]-B[j])
    dist=dist+abs(B[N-2])
    print(dist)


### FIXED CODE ###

N=int(input())
A= [int(i) for i in input().split()]
A.insert(0,0)
A.insert(N+1,0)
dist=0
for i in range(N+1):
    dist=dist+abs(A[i]-A[i+1])

for i in range(1,N+1):
    s=dist+abs(A[i-1]-A[i+1])-(abs(A[i-1]-A[i])+abs(A[i]-A[i+1]))
    print(s)
### BUGGY CODE ###

import sys

k=int(input())
if k%2==0:
  print(-1)
  sys.exit(0)
c=1
m=7%k
while 1:
  if m==0:
    print(c)
    sys.exit(0)
  m=m*10+7
  m%=k
  c+=1






### FIXED CODE ###

import sys

k=int(input())
if k%2==0:
  print(-1)
  sys.exit(0)
c=1
m=7%k
while 1:
  if m==0:
    print(c)
    sys.exit(0)
  if c>k+1:
    print(-1)
    sys.exit(0)
  m=m*10+7
  m%=k
  c+=1
### BUGGY CODE ###

N = int(input())
# N, K = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N - 1)]

ans = [-1] * N
W = [[0 for __ in range(N)] for _ in range(N)]
P = [[] for _ in range(N)]
for l in L:
    u, v, w = l
    W[u - 1][v - 1] = w
    P[u - 1].append(v - 1)
    P[v - 1].append(u - 1)

ans[0] = 0
F = [0]
it = 0
while len(F) > it:
    u = F[it]
    it += 1
    for v in P[u]:
        if ans[v] != -1:
            continue

        w = W[u][v] if u < v else W[v][u]
        ans[v] = ans[u] if w % 2 == 0 else 1 - ans[u]
        F.append(v)

for a in ans:
    print(a)



### FIXED CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N):
    res = 0
    while N != 0:
        b = format(N, "b").count("1")
        N %= b
        res += 1
    return res


def main():
    N = int(input())
    F = [[] for _ in range(N)]

    for _ in range(N - 1):
        u, v, w = read_values()
        u -= 1
        v -= 1
        F[u].append((v, w % 2))
        F[v].append((u, w % 2))

    D = [0] * N
    stack = [(0, 0, -1)]

    while stack:
        a, d, p = stack.pop()
        D[a] = d % 2

        for b, w in F[a]:
            if b == p:
                continue
            stack.append((b, (d + w) % 2, a))
    
    for d in D:
        print(d)


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

n=int(input())
a=list(map(int,input().split()))
i=0
j=0
for i in range(len(a)):
    c=0
    for j in range(len(a)):
        if a[j]==i+1:
            c=c+1
    print(c)
    print('\n')
print(0)

### FIXED CODE ###

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

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
uv=[list(map(int,input().split())) for i in range(n-1)]
edge=defaultdict(list)
for i in range(n-1):
    u,v=uv[i]
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

d=deque([[1,[float('inf')]]])
itta=[0]*(n+1)
lislist=[0]*(n+1)
while d:
    now,lis=d.pop()
    itta[now]=1
    # print(now,lis)
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
    else:
        lis[bisect.bisect_left(lis, a[now-1])]=a[now-1]
    lislist[now]=lis
    for i in edge[now]:
        if itta[i]==0:
            d.append([i,lis[:]])
# print(lislist)
for i in range(n):
    print(len(lislist[i+1]))

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(1000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
uv=[list(map(int,input().split())) for i in range(n-1)]
edge=defaultdict(list)
for i in range(n-1):
    u,v=uv[i]
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

itta=[0]*(n+1)
# lislist=[0]*(n+1)

def dfs(now,lis):
    stk=0
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
        stk="pop"
    else:
        tmp=bisect.bisect_left(lis, a[now-1])
        stk=[tmp,lis[tmp]]
        lis[tmp]=a[now-1]
    
    # print(now,lis)
    itta[now]=len(lis)
    for i in edge[now]:
        if itta[i]==0:
            dfs(i,lis)
    
    if stk=="pop":
        lis.pop()
    else:
        lis[stk[0]]=stk[1]

dfs(1,[float('inf')])

# print(itta)
for i in range(n):
    print(itta[i+1])
### BUGGY CODE ###

import heapq

def myprim_heap(graph, n):
    #始点sから各頂点への最短距離
    INF = 10**9
    d = [INF] * n
    used = [False] * n #True:未確定
    s = 0
    d[s] = 0
    used[s] = True
    res = 0
    edgelist = []
    for e in graph[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]:
            continue
        res += minedge[0]
        v = minedge[1]
        used[v] = True
        for e in graph[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist, e)
    return res


n = int(input()) 
graph = [[] for _ in range(n)]
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

ixy = sorted(ixy, key=lambda x:(x[1], x[2]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = abs(ixy[i][1] - ixy[i+1][1])
    graph[j].append([d,k])
    graph[k].append([d,j])

ixy = sorted(ixy, key=lambda x:(x[2], x[1]))
for i in range(n-1):
    j, k = ixy[i][0], ixy[i+1][0]
    d = abs(ixy[i][2] - ixy[i+1][2])
    graph[j].append([d,k])
    graph[k].append([d,j])

res = myprim_heap(graph, n)
print(res)

### FIXED CODE ###

from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = set()
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
    
# csr形式に直す
row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)
### BUGGY CODE ###

N,M=map(int,input().split())
a=[]
b=[]
flag=0
for i in range(M):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)
for j in range(M):
    if a[j]==1:
        for k in range(M):
            if a[k]==b[j]:
                if b[k]==N:
                    flag += 1
                else:
                    pass
            else:
                pass
    else:
        pass
if flag>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

N,M=map(int,input().split())
island=[[] for i in range(N)]
for j in range(M):
    c,d=map(int,input().split())
    island[d-1].append(c)
    island[c-1].append(d)
f = 0
for k in range(N):
    if 1 in island[k]:
        if N in island[k]:
            f += 1
            break
        else:
            pass
    else:
        pass
if f>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

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

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 0
for i in range(N):
    for j in range(N-1, i, -1):
        if A[j] < A[j-1]:
            A[j], A[j-1] = A[j-1], A[j]
            x += 1
M = 10**9 + 7

y = 0
NN = N*2
for i in range(NN):
    for j in range(NN-1, i, -1):
        if AA[j] < AA[j-1]:
            AA[j], AA[j-1] = AA[j-1], AA[j]
            y += 1

a = (K*x) % M
b = (y - 2*x) * int( (K*(K-1)//2) % M)
ans = ((a+b)  % M)
print(int(ans))

### FIXED CODE ###

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

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 0
for i in range(N):
    for j in range(i+1, N):
        if A[j] < A[i]:
            x += 1
M = 10**9 + 7

y = 0
NN = N*2
for i in range(NN):
    for j in range(i+1, NN):
        if AA[j] < AA[i]:
            y += 1

a = (K*x)
b = (y - 2*x) * (K*(K-1)//2)
ans = ((a+b)  % M)
print(int(ans))
### BUGGY CODE ###

def main():
    N=int(input())
    a=[]
    for i in range(N):
        a.append(list(map(int,input().split())))
    mod=10**9+7
    
    dp=[0]*(2**N)
    dp[0]=1
    for i in range(1,2**N):
        m=bin(i).count("1")
        for j in range(N):
            if i>>j&1==1 and a[m-1][j]==1:
                dp[i]+=dp[i-2**j]
        dp[i]%=mod
    
    print(dp[-1])

if __name__=="__main__":
    main()
    

### FIXED CODE ###

def main():
    N=int(input())
    a=[]
    for i in range(N):
        a.append(list(map(int,input().split())))
    mod=10**9+7

    dp=[0]*(2**N)
    dp[0]=1
    for i in range(1,2**N):
        m=[j for j in range(N) if i>>j &1==1]
        for j in m:
            dp[i]+=dp[i-2**j]*a[len(m)-1][j]
        dp[i]%=mod
    
    print(dp[-1])

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

def main():
  s,q,*r = [list(k.split()) for k in open(0)]
  s=s[0]
  p = False
  for x in r:
    if len(x)==1:
      p = not p
      continue
    if (p==False and x[1]=='1') or (p==True and x[1]=='2'):
        s = x[2] + s
    else:
        s = s + x[2]
  print("".join(s) if p==False else "".join(s)[::-1])
  
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from collections import deque
  
  s,q,*r = [list(k.split()) for k in open(0)]
  que = deque(s[0])
  p = False
  for x in r:
    if len(x)==1:
      p = not p
      continue
    if (p==False and x[1]=='1') or (p==True and x[1]=='2'):
        que.appendleft(x[2])
    else:
        que.append(x[2])
  print("".join(que) if p==False else "".join(que)[::-1])
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

import heapq
xs,yx,xt,yt = map(int,input().split())
N = int(input())
l = [[],[xs,yx,0],[xt,yt,0]]
for i in range(N):
  l.append(list(map(int,input().split())))
##距離リスト
d = [[0]*(N+3) for _ in range(N+3)]
for i in range(1,N+3):
  d[i][i] = 0
#O(10**6)
for i in range(1,N+3):
  for j in range(i+1,N+3):
    sa = (l[i][0]-l[j][0])**2 + (l[i][1]-l[j][1])**2
    kyori = max(0,sa**(1/2)-l[i][2]-l[j][2])
    d[i][j] = kyori
    d[j][i] = kyori

md = [float("inf")]*(N+3)
heap = [[d[1][i],i] for i in range(2,N+3)]
heapq.heapify(heap)
for i in range(1,N+3):
  md[i]=d[1][i]
cnt = 0
seen = [False]*(N+3)
seen[1] = True
while len(heap)>0:
  v = heapq.heappop(heap) 
  if seen[v[1]] == False:
    for i in range(1,N+3):
      if md[i] > md[v[1]]+d[i][v[1]]:
        md[i] = md[v[1]]+d[i][v[1]]
        seen[v[1]] = True
        heapq.heappush(heap,[md[i],i])
print(md[2])      

### FIXED CODE ###

xs,yx,xt,yt = map(int,input().split())
N = int(input())
l = [[],[xs,yx,0],[xt,yt,0]]
for i in range(N):
  l.append(list(map(int,input().split())))
##距離リスト
d = [[0]*(N+3) for _ in range(N+3)]
for i in range(1,N+3):
  d[i][i] = 0
#O(10**6)
for i in range(1,N+3):
  for j in range(i+1,N+3):
    sa = (l[i][0]-l[j][0])**2 + (l[i][1]-l[j][1])**2
    kyori = max(0,sa**(1/2)-l[i][2]-l[j][2])
    d[i][j] = kyori
    d[j][i] = kyori

md = [float("inf")]*(N+3)
h = [i for i in range(1,N+3)]
for i in range(1,N+3):
  md[i]=d[1][i]
seen = [False]*(N+3)
seen[1] = True
while True:
  #vを出す
  v = -1
  for i in h:
    if seen[i] == False and v == -1:
      v = i
    elif seen[i] == False and md[i] < md[v]:
      v = i
  if v == -1:
    break
  seen[v] = True
  for j in range(1,N+3):
    md[j] = min(md[j],md[v]+d[v][j])
print(md[2])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys



def solve(H: int, W: int, A: "List[str]"):
    current = set()
    for i in range(H):
        for j in range(W):
            if not A[i][j]:
                current.add((i,j))
    def appendIfPossible(i,j,s):
        if i >= 0 and i < H and j >=0 and j < W and A[i][j]:
            s.add((i,j))
            A[i][j] = False
    count = 0
    while True:
        next = set()
        for c in current:
            appendIfPossible(c[0]-1,c[1],next)
            appendIfPossible(c[0]+1,c[1],next)
            appendIfPossible(c[0],c[1]-1,next)
            appendIfPossible(c[0],c[1]+1,next)
        current = next
        count+= 1
        if len(next) == 0:
            break
    print(count-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [list(map(lambda x:x=='.',next(tokens))) for _ in range(H)]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys



def solve(H: int, W: int, A: "List[str]"):
    current = set()
    for i in range(H):
        for j in range(W):
            if not A[i][j]:
                current.add((i,j))
    def appendIfPossible(i,j,s):
        if i >= 0 and i < H and j >=0 and j < W and A[i][j]:
            s.add((i,j))
            A[i][j] = False
    count = 0
    while True:
        next = set()
        for c in current:
            appendIfPossible(c[0]-1,c[1],next)
            appendIfPossible(c[0]+1,c[1],next)
            appendIfPossible(c[0],c[1]-1,next)
            appendIfPossible(c[0],c[1]+1,next)
        current = next
        count+= 1
        if len(next) == 0:
            break
    print(count-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [list(map(lambda x:x=='.',next(tokens))) for _ in range(H)]  # type: "List[str]"
    solve(H, W, A)

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

import copy
S = input()
S = S[::-1]
dp = [0 for _ in range(13)]
dp[0] = 1

mod = int(1e9+7)

def calc(dp,i,k):
  dpw = [0 for _ in range(13)]
  if S[i] == '?':
    X = [i for i in range(10)]
  else:
    X = [int(S[i])]
  for j in range(13):
    for x in X:
      dpw[(j+x*k)%13] += dp[j]  
      dpw[(j+x*k)%13] %= mod
  return dpw

keta = 1
for i in range(len(S)):
  dp = calc(dp,i,keta)
  keta = keta * 10 % 13

#print(dp)
print(dp[5])
#print(sum(dp))

### FIXED CODE ###

import copy
S = input()
S = S[::-1]
dp = [0 for _ in range(13)]
dp[0] = 1

mod = int(1e9+7)

def calc(dp,i,k):
  dpw = [0 for _ in range(13)]
  if S[i] == '?':
    X = [i for i in range(10)]
  else:
    X = [int(S[i])]
  for j in range(13):
    for x in X:
      dpw[(j+x*k)%13] += dp[j]  
      dpw[(j+x*k)%13] %= mod
  return dpw

keta = 1
for i in range(len(S)):
  dp = calc(dp,i,keta)
  keta = keta * 10 % 13

#print(dp)
print(dp[5])
#print(sum(dp))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(lambda pi: (int(pi) + 1) / 2, input().split()))
ex = []
for i in range(n-k+1):
    ex.append(sum(p[i:i+k]))
print(max(ex))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(lambda pi: (int(pi) + 1) / 2, input().split()))
ex = sum(p[:k])
mx = ex
for i in range(n - k):
    ex += p[i + k] - p[i]
    if mx < ex:
        mx = ex
print(mx)