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

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

p=list(map(int,input().split()))
c=list(map(int,input().split()))

check=[0]*n
group=[]

for i in range(n):
    tmp=i
    if check[tmp]==0:
        tmp_group=[]
        while check[tmp]==0:
            tmp_group.append(tmp)
            check[tmp]=1
            tmp=p[tmp]-1

        group.append(tmp_group)

ans="start"

#startの最低とgoalの最高の和
for item in group:
    
    #一周すると何になるか。これはどこスタートでも同じ
    circle=0
    cnt=k
    if len(item)<k:
        for v in item:
            circle+=c[v]
        cnt=k-len(item)
    
    #一周した後のあまりで最強を探す


    goal=(-1)*(10**18)
    
    #startは各groupのindexが入ってる
    for start in range(len(item)):
        tmp=0
        #print("start",item,start,cnt)
        for i in range(start,start+cnt):
            #print(">>",i)
            tmp+=c[item[i%len(item)]]
            #print(item[i%len(item)],c[item[i%len(item)]])
            goal=max(goal,tmp)

    #print(item,circle,goal)
    if ans=="start":
        ans=goal+max(0,circle)
    else:
        ans=max(ans,goal+max(0,circle))

print(ans)














### FIXED CODE ###

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

p=list(map(int,input().split()))
score=list(map(int,input().split()))

group_score=[]
checked=[0]*n

for i in range(n):
    if checked[i]==0:
        tmp_group=[]
        tmp=i
        while checked[tmp]==0:
            checked[tmp]=1
            tmp_group.append(score[tmp])
            tmp=p[tmp]-1
        group_score.append(tmp_group)



#aryの中から連続するk個選択するときの最大
def calc(k):
    if k==0:
        return 0
    global group
    ans="INF"
    for i in range(len(group)):
        tmp=0
        for j in range(k):
            tmp+=group[(i+j)%len(group)]
            if ans=="INF":
                ans=tmp
            else:
                if ans<tmp:
                    ans=tmp
    return ans

ans=score[0]
for group in group_score:
    #一周以上する場合
    if len(group)<k:
        cycle=sum(group)
        if cycle>0:
            cycle_sum=cycle*(k//len(group))
            tmp=calc(k%len(group))
            ans=max(ans,cycle_sum+tmp)

            if k//len(group)>=2:
                cycle_sum=cycle*(k//len(group)-1)
                tmp=calc(len(group))
                ans=max(ans,cycle_sum+tmp)
          

        tmp=calc(len(group))
        ans=max(ans,tmp)



    #一周しない場合k)
    else:
        tmp=calc(k)
        ans=max(ans,tmp)

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

#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for _ in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

A,B,N = map(int,sys.stdin.readline().split())

m = -float("inf")
for i in range(N+1):
    m = max(m,math.floor(A*i/B)-A*math.floor(i/B))
print(m)
# x = B//2
# print(math.floor(A*x/B)-A*math.floor(x/B))


### FIXED CODE ###

#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for _ in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

A,B,N = map(int,sys.stdin.readline().split())

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

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

I = []
for i in range(N-1):
    I.append(X[i+1]-X[i])

M = X[N-1]-X[0]
I_srt = sorted(I)
I_srt.reverse()


ans = min([(M-sum(I_srt[:i]))*A + B*i for i in range(N)])

print(ans)


### FIXED CODE ###

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

I = []
for i in range(N-1):
    I.append(X[i+1]-X[i])

M = X[N-1]-X[0]
I_srt = sorted(I)
I_srt.reverse()

I_sum = [0]
for i in range(N-1):
    I_sum.append(I_srt[i]+I_sum[i])


ans = min([(M-I_sum[i])*A + B*i for i in range(N)])

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

import sys #追加
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())

from collections import defaultdict
dic = defaultdict(list)


for _ in range(n-1):
    a,b = map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)


dic2 = defaultdict(int)

for _ in range(q):
    p,x = map(int,input().split())
    dic2[p-1] += x

ansl = [0 for i in range(n)]
used = [-1 for i in range(n)]
used[0] = 1
que = [0]
while que:
    pos = que.pop()
    used[pos] = 1
    for p in dic[pos]:
        if used[p] == -1:
            ansl[p] = ansl[pos] + dic2[pos]
            que.append(p)


for idx, a in enumerate(ansl):
    print(a + dic2[idx])





### FIXED CODE ###

n,q = map(int,input().split())
m = [[] for i in range(n)]
for _ in range(n-1):
   a,b = map(int,input().split())
   m[a-1].append(b-1)
   m[b-1].append(a-1)

from collections import defaultdict
dic = defaultdict(int)
for _ in range(q):
   p,x = map(int,input().split())
   dic[p-1] += x

ans = [0 for i in range(n)]
ans[0] = dic[0]

used = [0 for i in range(n)]
used[0] = 1
quu = [0]
while quu:
   k = quu.pop()
   for l in m[k]:
      if used[l] == 0:
         used[l] = 1
         quu.append(l)
         ans[l] = ans[k] + dic[l]

for i in ans:
   print(i)
### BUGGY CODE ###

class WarshallFroyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float('inf')] * N for _ in range(N)]

    def add(self, u, v, c, directed=False):
        """
        Valid only for '0-indexed' graphs!
        add an edge from u to v with cost d
        """
        if directed == False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self, DetectNegativeCycle=False):
        """
        Change self.d to self.d[i][j] = (minimal cost from i to j)
        If self.d[i][j] < 0, this graph has negative loops
        """
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        if DetectNegativeCycle == True:
            hasNegativeCycle = False
            for i in range(self.N):
                if self.d[i][i] < 0:
                    hasNegativeCycle = True
                    break
        for i in range(self.N):
            self.d[i][i] = 0
        if DetectNegativeCycle == True:
            return hasNegativeCycle, self.d
        else:
            return None, self.d


"""
classを使いまわすと遅い？？？
以下は直接実装にしてみた。
"""

N, M, L = map(int, input().split())
dp = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#rint('distance={}'.format(dp))


dp2 = [[float('inf')] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if dp2[s-1][t-1] != float('inf'):
        print(dp2[s-1][t-1] - 1)
    else:
        print(-1)


### FIXED CODE ###

inf = 10 ** 15

N, M, L = map(int, input().split())
dp = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for i in range(N):
    dp[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print('distance={}'.format(dp))


dp2 = [[inf] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    cost = dp2[s-1][t-1]
    if cost != inf:
        print(cost - 1)
    else:
        print(-1)
### BUGGY CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
h_dict = {}
for i, name in enumerate(h):
    h_dict[i] = name

ab = []
for _ in range(m):
    ab.append(list(map(int, input().split())))
for l in range(len(ab)):
    ab.append([ab[l][1], ab[l][0]])

flg_bad = {}
for j in ab:
    for i in range(len(h_dict)):
        if i in flg_bad:
            continue
        if i+1 == j[0]:
            if h[i] <= h[j[1]-1]:
                flg_bad.setdefault(i, 1)
                break

print(len(h) - len(flg_bad))


### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
h_dict = {}
for i, name in enumerate(h, 1):
    h_dict[i] = name

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

flg_bad = set()
for j in ab:
    if h_dict[j[0]] < h_dict[j[1]]:
        flg_bad.add(j[0])
    elif h_dict[j[0]] > h_dict[j[1]]:
        flg_bad.add(j[1])
    elif h_dict[j[0]] == h_dict[j[1]]:
        flg_bad.add(j[0])
        flg_bad.add(j[1])

print(len(h) - len(flg_bad))
### BUGGY CODE ###

N, K = [int(nk) for nk in input().split()]
A = [int(a) for a in input().split()]

A_set = list(set(A))
if len(A_set) <= K:
  print(0)
else:
  AA = [A.count(i) for i in A_set]
  AA.sort()
  ans = sum(AA[:-K])
  print(ans)

### FIXED CODE ###

N, K = [int(nk) for nk in input().split()]
A = [int(a) for a in input().split()]

A_set = list(set(A))
if len(A_set) <= K:
  print(0)
else: # len(A_set) > K:
  dictionary = {}
  for n in A_set:
    dictionary[n] = 0
  for m in A:
    dictionary[m] += 1
  
  dict_val = list(dictionary.values())
  dict_val.sort(reverse = True)
  ans = N - sum(dict_val[:K])
  print(ans)
### BUGGY CODE ###

N = int(input())
lst = list(map(int, input().split()))
lst.sort()
lst.append(10**10)
total = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        cnt = 0
        k = j+1
        while lst[j]+lst[i] > lst[k]:
            cnt += 1
            k += 1
        total += cnt
print(total)


### FIXED CODE ###

import bisect
N = int(input())
lst = list(map(int, input().split()))
lst.sort()
total = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        x = bisect.bisect_left(lst, lst[i]+lst[j])
        total += x-j-1
print(total)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-02-21 01:20:19 +0900
# LastModified: 2020-02-21 02:04:42 +0900
#


import numpy as np
import heapq
def make_matrix(matrix,a,b,c):
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c

def initial_signal(i,matrix):
    d = [float("inf")]*(matrix.shape[0])
    d[i] = 0
    Q = []
    heapq.heappush(Q,(0,i))
    return d,Q

def relax(matrix,u,v,d,Q):
    if d[v] > d[u]+matrix[u][v]:
        d[v] = d[u]+matrix[u][v]
        heapq.heappush(Q, (d[v],v))


def dijkstra(i,matrix):
    d,Q = initial_signal(i,matrix)
    while Q:
        cost,u = heapq.heappop(Q)
        if d[u]<cost:
            continue
        for v in range(matrix.shape[0]):
            if matrix[u][v]!=0:
                relax(matrix,u,v,d,Q)
    return d
    

def main():
    N,M = map(int, input().split())
    matrix = np.zeros((N,N),dtype=np.int32)
    for _ in range(M):
        a,b,c = map(int,input().split())
        make_matrix(matrix,a,b,c)
    shortest = []
    for i in range(matrix.shape[0]):
        shortest.append(dijkstra(i,matrix))
    ans=0
    for i in range(N):
        for j in range(N):
            if matrix[i][j]>shortest[i][j]:
                ans+=1
    print(ans//2)


if __name__ == "__main__":
    main()


### FIXED CODE ###

## https://atcoder.jp/contests/abc051/submissions/3281251
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]
    
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    
    while q:
        cost, cur_node = heapq.heappop(q)
        
        if dist[cur_node] < cost:
            continue
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((c, b))
        adj[b].append((c, a))
    shortest = []
    for i in range(n):
        shortest.append(dijkstra(adj, n, i))
    ans = 0
    for i in range(n):
        for cost, j in adj[i]:
            if cost > shortest[i][j]:
                ans += 1
    print(ans // 2)
                                                                                                                                                                                                     
if __name__=='__main__':
    main()
### BUGGY CODE ###

import math
a,b=map(int,input().split())
c=list(map(int,input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort()
    return divisors
d=make_divisors(sum(c))


m=1
for i in d:
  d=[0 for j in range(a)]
  for j in range(a):
    d[j]=c[j]%i
  d.sort()
  for j in range(a):
    k=sum(d[:j]) 
    l=(a-j)*i-sum(d[j:])
    if k==l and k+l<=b*2:
      m=max(i,m)
      break
print(m)


### FIXED CODE ###

import math
from itertools import accumulate
a,b=map(int,input().split())
c=list(map(int,input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse = True)
    return divisors
d=make_divisors(sum(c))


m=1
for i in d:
  e=[]
  for j in range(a):
    e.append(c[j]%i)
  e.sort()
  acc_m = list(accumulate(e))
  e=[i-e[j] for j in range(a)]
  acc_p = list(accumulate(e))
  for j in range(a):
    k=acc_m[j]
    l=acc_p[-1]-acc_p[j]
    if k==l and k+l<=b*2:
      print(i)
      exit()
### BUGGY CODE ###

MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


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

if A < B:
    A, B = B, A

n = 2 * min(K // A + 2, N + 1) + 3

lst = Factorial(N + 1, MOD) #O(N)
N_factrorial = lst.factorial(N)
l_ifactorial = lst.ifactorial

def calc(a, b):
    tmp = 0
    G = min(a, b) #緑色の最大値
    # print ('G=', G)
    for green in range(G, -1, -1):
        red = a - green
        blue = b - green
        none_color = N - red - green - blue
        # print (red, green, blue, none_color)
        if none_color < 0:
            break
        tmp += ((((N_factrorial * l_ifactorial(red) % MOD) * l_ifactorial(green) % MOD) * l_ifactorial(blue) % MOD) * l_ifactorial(none_color) % MOD)
        tmp %= MOD
    return tmp

def count(a, b):
    if a + b > 2 * N:
        return 0
    # print ('to calc')
    return calc(a, b)

ans = 0
for a in range(n): #Aの数
    if A * a > K:
        break
    if (K - A * a) % B != 0:
        continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

print (ans)

### FIXED CODE ###

import numpy as np
MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

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

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

if A < B:
    A, B = B, A

# n = 2 * min(K // A + 2, N + 1) + 3
n = min((K + A - 1) // A, N) + 1
lcm = A * B // gcd(A, B)
step = lcm // A

c = Factorial(N + 1, MOD).comb #O(N)

def calc(a, b):
    if a > b:
        a, b = b, a #必ずaのほうが小さくなる
    return (c(N, a) * c(N, b)) % MOD


def count(a, b):
    if a <= N and b <= N:
        return calc(a, b)
    return 0

def maike_satrt(step):
    for i in range(step):
        if (K - A * i) % B == 0:
            return i

start = maike_satrt(step)
# print (start, n)
ans = 0
for a in range(start, n, step): #Aの数
    if A * a > K:
        break
    # if (K - A * a) % B != 0:
    #     continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

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

N = int(input())
flag = 0
if N < 2:
    for a in range(1,3501):
        if flag == 1:
            break
        for b in range(1,1751):
            M = (4*a*b - N*a - N*b)
            C = N*a*b
            #print(M,C,C/M)
            if M < 0 :
                continue
            elif M != 0:
                if C//M == C/M:
                    c = C//M
                    print(a,b,c)
                    flag = 1
                    break
else:
    A = [i for i in range(1,3501)]
    B = [i for i in range(1,3501)]
    for a in A[::-1]:
        if flag == 1:
            break
        for b in B[::-1]:
            M = (4*a*b - N*a - N*b)
            C = N*a*b
            #print(M,C,C/M)
            if M < 0 :
                continue
            elif M != 0:
                if C//M == C/M:
                    c = C//M
                    print(a,b,c)
                    flag = 1
                    break


### FIXED CODE ###

import sys
N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if 4*n*h > N*n + N*h and (N*n*h) % (4*n*h-N*h-N*n) == 0:
            w =  (N*n*h) // (4*n*h-N*h-N*n)
            print(n,h,w)
            sys.exit()
### BUGGY CODE ###

from itertools import accumulate
from math import ceil

# 位置xにあるゴミをi番目に拾うときの、追加コスト
def E(i, x):
    if i > 2:
        return (2 * i + 1) * x
    else:
        return 5 * x

N, X = map(int, input().split())
xs = list(map(int, input().split()))

accXs = [0] + list(accumulate(reversed(xs)))

# ロボット台数kを全て試す
ans = float('inf')
for k in range(1, N + 1):
    cost = (N + k) * X
    for i in range(1, ceil(N / k) + 1):
        # i番目に拾うゴミについて、まとめて計算する
        cost += E(i, accXs[min(N, i * k)] - accXs[(i - 1) * k])
    ans = min(ans, cost)

print(ans)


### FIXED CODE ###

from itertools import accumulate
from math import ceil

N, X = map(int, input().split())
xs = list(map(int, input().split()))

accXs = [0] + list(accumulate(reversed(xs)))

# ロボット台数kを全て試す
ans = float('inf')
for k in range(1, N + 1):
    cost = (N + k) * X

    # i番目に拾うゴミについて、追加コストをまとめて計算する
    cost += 5 * (accXs[k] - accXs[0])

    m = ceil(N / k)
    for i in range(2, m):
        cost += (2 * i + 1) * (accXs[i * k] - accXs[(i - 1) * k])

    cost += (2 * m + 1) * (accXs[N] - accXs[(m - 1) * k])

    ans = min(ans, cost)

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

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

n=int(input())
C=[];S=[];F=[]
for i in range(n-1):
    c,s,f=map(int,input().split())
    C.append(c)
    S.append(s)
    F.append(f)
for start in range(n-1):
    i=start
    time=S[start]
    while i < n-1:
        while time % F[i] != 0 or time<S[i]:
            time += 1
        time += C[i]
        i+=1
    print(time)
print(0)


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

n=int(input())
C=[];S=[];F=[]
for i in range(n-1):
    c,s,f=map(int,input().split())
    C.append(c)
    S.append(s)
    F.append(f)
for start in range(n-1):
    i=start
    time=S[start]
    while i < n-1:
        while time % F[i] != 0 or time<S[i]:
            time += 1
        time += C[i]
        i+=1
    print(time)
print(0)
### BUGGY CODE ###

# AGC033A - Darker and Darker
def main():
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    B = [[0 if i == "#" else -1 for i in a] for a in A]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    cur, flg = 0, 1
    while flg:
        flg = 0
        for x, b in enumerate(B):
            for y, i in enumerate(b):
                if i != cur:
                    continue
                for dx, dy in dxy:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                        B[nx][ny] = cur + 1
                        flg = 1
        cur += 1
    ans = cur - 1
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# AGC033A - Darker and Darker
from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        0 0 0    1 1 1
        0 1 0 -> 1 0 1
        0 0 0    1 1 1
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = list(list(input()) for _ in range(h))
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    print(D.max())


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

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

data = []
for a,b in ab:
  if a == 1:
    data.append(b)

for a,b in ab:
  if a in data and b == N:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()

data = [0]*N
for i in range(M):
  a,b = IL()
  if a == 1:
    if data[b]==1:
      print("POSSIBLE")
      break
    else:
      data[b]=1
  if b == N:
    if data[a]==1:
      print("POSSIBLE")
      break
    else:
      data[a]=1
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))

    ep = [0] * N
    for i, x in enumerate(p):
        t = [x for x in range(1, x + 1)]
        e = sum(t) / x
        ep[i] = e

    tmp = sum(ep[:K])
    ans = tmp

    for i in range(K, N):
        tmp = tmp + ep[i] - ep[i - K]
        ans = max(tmp, ans)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    
    pi_table = [0] + [(i * (i + 1) // 2) / i for i in range(1,1001)]
    
    pe = [None] * N
    for i in range(N):
        pe[i] = pi_table[p[i]]
    
    tmp = sum(pe[:K])
    ans = tmp
    for i in range(K, N):
        tmp += (pe[i] - pe[i - K])
        ans = max(ans, tmp)
        
    print(ans)



if __name__ == "__main__":
    main()