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

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

start = -1
end = A[-1] * F[0]

def check(now):
    cnt = 0
    for a, f in zip(A, F):
        cnt += max(0, a-now//f)
        # eatable = now//f
        # if eatable < a:
        #     cnt += a - eatable
    return cnt <= K
    # if cnt > K:
    #     return False
    # return True

while end > start + 1:
    now = (start + end) // 2
    if check(now):
        end = now
    else:
        start = now

print(end)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

q = [0] * N
start = 0
end = 0
for i in range(N):
    q[i] = A[i] * F[i]
    end = max(end, q[i])

def check(now, K):
    cnt = 0
    for i in range(N):
        if q[i] - now > 0:
            cnt += (q[i] - now + F[i] - 1) // F[i]
            if cnt > K:
                return False
    return True

now = end // 2
while end > start + 1:
    if check(now, K):
        end = now
    else:
        start = now
    now = (start + end) // 2

if check(start, K):
    print(start)
else:
    print(end)
### BUGGY CODE ###

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

m=10**9+7

dp=[ [0]*(k+1) for _  in range(n+1) ]
dp[0][0]=1

dp_sum=[ [0]*(k+1) for _  in range(n+1) ]

for i in range(n):
    for j in range(k+1):
        if j==0:
            dp_sum[i][j]=1
        else:
            dp_sum[i][j]= dp_sum[i][j-1]+dp[i][j]
        if j-a[i]>0:
            dp[i+1][j]= dp_sum[i][j] - dp_sum[i][j-a[i]-1]
        else:
            dp[i+1][j]= dp_sum[i][j]

print(dp[n][k]%m)

### FIXED CODE ###

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

m=10**9+7

dp=[ [0]*(k+1) for _  in range(n+1) ]
dp[0][0]=1

dp_sum=[ [0]*(k+1) for _  in range(n+1) ]

for i in range(n):
    for j in range(k+1):
        if j==0:
            dp_sum[i][j]=1
        else:
            dp_sum[i][j]= (dp_sum[i][j-1]+dp[i][j])%m
        if j-a[i]>0:
            dp[i+1][j]= (dp_sum[i][j] - dp_sum[i][j-a[i]-1])%m
        else:
            dp[i+1][j]= (dp_sum[i][j])%m

print(dp[n][k]%m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200100)

def abc157_d():
    N, M, K = map(int, input().split())
    fr = [set() for _ in range(N)]
    bl = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        fr[a].add(b)
        fr[b].add(a)
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        bl[c].add(d)
        bl[d].add(c)

    def dfs(nd, lb):
        nonlocal label, gr
        label[nd] = lb
        gr[lb].add(nd)
        for ch in fr[nd]:
            if label[ch] != -1: continue
            dfs(ch, lb)

    label = [-1] * N
    lb = 0
    gr = []
    for i in range(N):
        if label[i] != -1: continue
        gr.append(set())
        dfs(i, lb)
        lb += 1

    ans = [0] * N
    for i in range(N):
        cand = gr[label[i]] - fr[i] - bl[i]
        ans[i] = len(cand) - 1
    print(*ans, sep=' ')

abc157_d()

### FIXED CODE ###

import sys
sys.setrecursionlimit(200100)

def abc157_d():
    N, M, K = map(int, input().split())
    fr = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        fr[a].add(b)
        fr[b].add(a)
    bl = []
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        bl.append((c,d))

    def dfs(nd, lb):
        nonlocal label, gr
        label[nd] = lb
        gr[lb] += 1
        for ch in fr[nd]:
            if label[ch] != -1: continue
            dfs(ch, lb)

    ans = [0] * N
    label = [-1] * N
    lb = 0
    gr = []
    for i in range(N):
        if label[i] != -1:
            ans[i] = gr[label[i]]
            continue
        gr.append(0)
        dfs(i, lb)
        ans[i] = gr[label[i]]
        lb += 1

    for c, d in bl:
        if label[c] == label[d]:
            ans[c] -= 1
            ans[d] -= 1

    for i in range(N):
        ans[i] -= len(fr[i]) + 1

    print(*ans, sep=' ')

abc157_d()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

MAX_INT = 2**62-1
sys.setrecursionlimit(10**5)

input = sys.stdin.readline


def n_input():
    return input().split()


# class ModOperation:

#     def __init__(self, mod):
#         self.mod = mod

#     def add(self, a, b):
#         return (a + b) % self.mod

#     def sub(self, a, b):
#         return (a - b) % self.mod

#     def mul(self, a, b):
#         m = self.mod
#         return ((a % m) * (b % m)) % m

#     def div(self, a, b):
#         m = self.mod
#         return self.mul(a, pow(b, m-2, m))


N = 2 * (10**5) + 1
MOD = 10**9 + 7

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre, cur] = num, ways
        return num, ways

    m = MOD
    f, fi = fact, fact_inv
    memo = {}

    for i in range(1, len(g)):
        print(dfs(None, i)[1])


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

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

    solve(g)


if __name__ == "__main__":

    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import reduce

MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(*args, mod=MOD):
    return reduce(lambda a, b: a * b % mod, args)


def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(dp[pre], dp[cur], fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        i = size[cur]
        temp = mul(ans[pre], f[n-i-1], fi[n-1], f[i], pow(dp[cur], m-2, m))
        ans[cur] = mul(f[n-1], temp, fi[n-i], dp[cur], fi[i-1])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

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

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()
### BUGGY CODE ###

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

change_points = [i for i in range(n) if i == 0 or s[i-1] != s[i]]
max_ = 0
for i in change_points:
    count = 0
    cur_k = 0
    is_zero = False
    for c in s[i:]:
        if len(s[i:]) < max_:
            break
        if c == '1':
            count += 1
            is_zero = False
        else:
            if is_zero:
                count += 1
            elif cur_k < k:
                cur_k += 1
                count += 1
                is_zero = True
            else:
                break
    if count > max_:
        max_ = count
print(max_)


### FIXED CODE ###

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

change_points = [i for i in range(n) if i == 0 or s[i-1] != s[i]]
change_points.append(n)
max_ = 0
for i, p in enumerate(change_points):
    if i == len(change_points) - 1:
        continue
    if s[p] == '0':
        if i == 0:
            idx = min(i + 2 * k, len(change_points) - 1)
            tmp = change_points[idx] - p
        else:
            continue
    else:
        idx = min(i + 2 * k + 1, len(change_points) - 1)
        tmp = change_points[idx] - p
    if tmp > max_:
        max_ = tmp

print(max_)
### BUGGY CODE ###

N, K = map(int, input().split())
inputs = [int(i) for i in input().split()]

dp = [10 ** 9 for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    if i == 1:
        dp[i] = abs(inputs[i] - inputs[i-1])
    else:
        tmp = 10 ** 9
        count = 0
        for j in range(i):
            if count >= K:
                break
            tmp = min(tmp, dp[i-(j+1)] + abs(inputs[i] - inputs[i-(j+1)]))
            count += 1
        dp[i] = tmp

print(dp[-1])


### FIXED CODE ###

import numpy as np


N, K = map(int, input().split())
inputs = np.array([int(i) for i in input().split()])

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = (dp[start:i] + abs(inputs[i] - inputs[start:i])).min()

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

from collections import deque

s = deque(list(input()))
q = int(input())
query = [input() for i in range(q)]

for i in range(q):
  temp = query[i].split()
  if int(temp[0]) == 1:
    s.reverse()
  else:
    if int(temp[1]) == 1:
      s.appendleft(temp[2])
    else:
      s.append(temp[2])

print(''.join(s))


### FIXED CODE ###

from collections import deque

def main():
  rev = False
  s = deque(input())
  q = int(input())
  query = tuple(input() for i in range(q))

  for i in range(q):
    temp = query[i].split()
    if int(temp[0]) == 1:
      rev = not rev
    else:
      if (int(temp[1]) == 1 and (not rev)) or (int(temp[1]) == 2 and rev):
        s.appendleft(temp[2])
      else:
        s.append(temp[2])

  if rev:
    s.reverse()

  print(''.join(s))

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

import heapq

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

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

hq = []
ans = 0
for i in reversed(range(M)):
    for x in jobs:
        if x[0] == M - i:
            heapq.heappush(hq, -x[1])
    if len(hq):
        ans += heapq.heappop(hq) * (-1)

print(ans)


### FIXED CODE ###

import heapq

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

jobs = []
for i in range(N):
    a, b = map(int, input().split())
    jobs.append((a, b))
jobs.sort()

hq = []
ans = 0
index = 0
for i in reversed(range(M)):
    for j in range(index, N):
        a, b = jobs[j]
        if a > M - i:
            break
        if a == M - i:
            heapq.heappush(hq, -jobs[j][1])
            index += 1

    if len(hq):
        ans += heapq.heappop(hq) * (-1)

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

#!/Library/Frameworks/Python.framework/Versions/3.5/bin/python3

s = input()
k = int(input())

all = set()
l = len(s)
for i in range(l):
    for j in range(i, l):
        all.add(s[i:j + 1])

print(sorted(all)[k - 1])


### FIXED CODE ###

#!/usr/bin/python3

s = input()
k = int(input())

l = len(s)
all = set()
for i in range(l):
    cnt = 0
    for j in range(i, l):
        all.add(s[i:j + 1])
        cnt += 1
        if cnt >= k:
            break

print(sorted(all)[k - 1])
### BUGGY CODE ###

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

for i in range(n):
    a, b = map(int, input().split())
    if not a in jobs.keys():
        jobs[a] = [b]
    else:
        jobs[a].append(b)

# print(jobs)

days = []
money_list = [0]
for i in range(1, m+1):
    # print('days', days)
    if i in jobs.keys():
        money_list.extend(jobs[i])
    # print(money_list)
    days.append(max(money_list))
    if max(money_list) != 0:
        money_list.remove(max(money_list))

print(sum(days))


### FIXED CODE ###

import heapq

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

for i in range(n):
    a, b = map(int, input().split())
    if not a in jobs.keys():
        jobs[a] = [-b]
    else:
        jobs[a].append(-b)
# print(jobs)
sum_money = 0
money_list = [0]
heapq.heapify(money_list)
for i in range(1, m+1):
    if i in jobs.keys():
        for money in jobs[i]:
            heapq.heappush(money_list, money)
    # print(money_list)
    max_money = -heapq.heappop(money_list)
    sum_money += max_money
    if max_money == 0:
        heapq.heappush(money_list, 0)
print(sum_money)
### BUGGY CODE ###

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

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(M//2+1)


for i in range(2, M//2+1):
    if checked[i]:
        continue
    if is_pairwise_coprime == False and i > m:
        break
    
    tmp = 0
    for j in range(N):
        if A[j]%i == 0:
            tmp += 1
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    if is_setwise_coprime == False:
        break
    
    n = i
    while n < M//2+1:
        checked[n] = 1
        n += i

if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)

# 素因数テーブルの作成
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因子をカウント
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        nums[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y-Ones < N:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
for i in range(M):
    A = sorted(A)
    A[N-1] //= 2
print(sum(A))

### FIXED CODE ###

import heapq

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
A = [i * -1 for i in A]
heapq.heapify(A)
for i in range(M):
    maxA = -1 * heapq.heappop(A)
    heapq.heappush(A,-1*(maxA//2))
print(-sum(A))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
# sx, sy = map(int, input().split())
# gx, gy = map(int, input().split())
# sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
c = [input() for i in range(H)]

def bfs():
    dist = [[float('inf') for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == float('inf'):
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[gx][gy]

ans = []
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                sx, sy = i, j
                gx, gy = k, l
                if c[sx][sy] == '#' or c[gx][gy] == '#':
                    continue
                ans.append(bfs())
                
ans = [i for i in ans if i != float('inf')]
print(max(ans))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
c = [input() for i in range(H)]

INF = -1

def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        # if p[0] == gx and p[1] == gy:
        #     break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    ret = -1
    for i in range(H):
        ret = max(ret, max(dist[i]))
    return ret

ans = -1
for i in range(H):
    for j in range(W):
            sx, sy = i, j
            if c[sx][sy] == '#':
                continue
            ans = max(ans, bfs())
print(ans)
### BUGGY CODE ###

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

def islike(num):
    num1 = num
    num2 = (num+1)//2
    if (is_prime(num1) and is_prime(num2)):
        return True
    else:
        return False

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    total = 0
    for m in range(l, r+1):
        if islike(m):
            total += 1
    print(total)

### FIXED CODE ###

# D submit
from math import sqrt
def sieve(n):
    if n<2:
        return [False]*(n+1)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return is_prime

n = int(1e5)
is_prime = sieve(n)

cnt = [0]*(n+1)
for i in range(1, n+1):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(cnt[r] - cnt[l-1])
### BUGGY CODE ###

import itertools

n = int(input())
A = list(map(int,input().split()))
A.sort()

def binary_search(l,r,v):
    while r >= l:
        h = (l+r) // 2
        if A[h] < v:
            l = h+1
        else:
            r = h-1
    return r

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = binary_search(0,n-1,A[i]+A[j])
        ans += a-j

print(ans) 


### FIXED CODE ###

import itertools
 
n = int(input())
A = list(map(int,input().split()))
A.sort()
 
def binary_search(l,r,v):
    while r >= l:
        h = (l+r) // 2
        if A[h] < v:
            l = h+1
        else:
            r = h-1
    return r
 
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = binary_search(j,n-1,A[i]+A[j])
        ans += a-j
 
print(ans)
### BUGGY CODE ###

n = int(input())
l = [int(c) for c in input().split()]
l.sort()
def bin_search(l, r, f):
    while r - l > 1:
        c = (l + r) // 2
        if f(c):
            r = c
        else:
            l = c
    return r

llen = len(l)
ans = 0
for i in range(llen):
    a = l[i]
    for j in range(i + 1, llen):
        b = l[j]
        s = a + b
        upper = bin_search(j, n, lambda x: l[x] >= s)
        #print(i, j, upper)
        ans += upper - (j + 1)
print(ans)



### FIXED CODE ###

n = int(input())
l = [int(c) for c in input().split()]
l.sort()
def bin_search(l, r, f):
    while r - l > 1:
        c = (l + r) // 2
        if f(c):
            r = c
        else:
            l = c
    return r

llen = len(l)
ans = 0
for i in range(llen):
    a = l[i]
    for j in range(i + 1, llen):
        b = l[j]
        s = a + b
        upper = bin_search(j, n, lambda x: l[x] >= s)
        #print(i, j, upper)
        ans += upper - (j + 1)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)

from bisect import bisect_left

for _ in range(m):
    x = A.pop()
    x = x//2
    A.insert(bisect_left(A, x), x)

print(sum(A))


### FIXED CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = map(lambda x: x * (-1), A)
A = sorted(A)

from heapq import heappush, heappop

for _ in range(m):
    x = heappop(A)
    heappush(A, (-1*x)//2*(-1))

print(sum(A)*(-1))
### BUGGY CODE ###

n=int(input())
s=input()
count=0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        if s[i]!=s[j]:
            for k in range(j+1,n):
                if j-i!=k-j and s[j]!=s[k] and s[i]!=s[k]:
                    count=count+1
print(count)

### FIXED CODE ###

n=int(input())
s=input()
count=0
A=[[0,0,0]for i in range(n)]
for i in range(0,n):
    if s[n-i-1]=="R":
        A[n-i-2][0]=A[n-i-1][0]+1
        A[n-i-2][1]=A[n-i-1][1]
        A[n-i-2][2]=A[n-i-1][2]
    if s[n-i-1]=="G":
        A[n-i-2][0]=A[n-i-1][0]
        A[n-i-2][1]=A[n-i-1][1]+1
        A[n-i-2][2]=A[n-i-1][2]
    if s[n-i-1]=="B":
        A[n-i-2][0]=A[n-i-1][0]
        A[n-i-2][1]=A[n-i-1][1]
        A[n-i-2][2]=A[n-i-1][2]+1
for i in range(0,n-3):
    s1=s[i]
    for j in range(i+1,n-1):
        s2=s[j]
        if s1!=s2:
            if s1=="R" and s2=="G":
                s3="B"
            elif s1=="G" and s2=="R":
                s3="B"
            elif s1=="R" and s2=="B":
                s3="G"
            elif s1=="B" and s2=="R":
                s3="G"
            elif s1=="B" and s2=="G":
                s3="R"
            elif s1=="G" and s2=="B":
                s3="R"
            if s3=="R":
                s4=0
            if s3=="G":
                s4=1
            if s3=="B":
                s4=2
            count=count+A[j][s4]
            if j+j-i+1<=n: 
                if s[j+j-i]==s3:
                    count=count-1
print(count)
### BUGGY CODE ###

K = int(input())
import math  
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans = ans + math.gcd(math.gcd(a,b),c)
print(ans)        

### FIXED CODE ###

K = int(input())
from math import gcd
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans = ans + gcd(gcd(a,b),c)
print(ans)
### BUGGY CODE ###

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

ans=0
tmp=0
for i in range(n-k+1):
    if tmp < sum(s[i:i+k]):
        tmp = sum(s[i:i+k])
        kukan = [i,i+k]

for i in range(kukan[0],kukan[1]):
    ans += (s[i]+1)/2
    
print(ans)

### FIXED CODE ###

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

ans=0
tmp=0
tmp2=sum(s[0:k])
kukan=[0,n]
for i in range(n-k):
    tmp2 -= s[i]
    tmp2 += s[k+i]
    if tmp < tmp2:
        tmp = tmp2
        kukan = [i+1,i+k+1]

for i in range(kukan[0],kukan[1]):
    ans += (s[i]+1)/2
    
print(ans)