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

from itertools import combinations

EPS = 1e-8

N, K, *XYC = map(int, open(0).read().split())
PC = [(complex(x, y), c) for x, y, c in zip(*[iter(XYC)] * 3)]


def intersection(A, r, B, s):
    D = B - A
    d = abs(D)

    cos_t = (d * d + r * r - s * s) / (2 * d * r)
    sin_t = max(1 - cos_t * cos_t, 0.0) ** 0.5

    R = r * complex(cos_t, sin_t)
    D /= d

    return (
        A + D * R,
        A + D * R.conjugate(),
    )


def is_ok(T):
    A = [p for p, _ in PC]
    for (p1, c1), (p2, c2) in combinations(PC, 2):
        A += intersection(p1, T / c1, p2, T / c2)

    return any(K <= sum(1 for p, c in PC if c * abs(a - p) < T + EPS) for a in A)


ng, ok = 0, 1000000
for _ in range(100):
    md = (ng + ok) / 2
    if is_ok(md):
        ok = md
    else:
        ng = md

print(ok)

### FIXED CODE ###

from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999995 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        for dx, dy in [(-0.5, -0.5), (-0.5, 0.5), (0.5, -0.5), (0.5, 0.5)]:
            Q.append((X + dx * r, Y + dy * r, r / 2))

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

N = int(input())
A = list(map(int, input().split()))
S=0
for i in range(N-1):
    for j in range(i+1,N):
        S=S+A[i]*A[j]%(1000000007)
print(S%(1000000007))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S=0
list = [0]*N
list[N-1]=A[N-1]%1000000007
for i in range(N-2,0,-1):
    list[i]=list[i+1]+A[i]%1000000007
    list[i]=list[i]%1000000007
for i in range(N-1):
    S=S+A[i]*list[i+1]%1000000007   
print(S%(1000000007))
### BUGGY CODE ###

"""

最後に登場したindexで考える
l以下のやつを除く
最後に登場したindexをBITにいれる

bit[i] = 最後に登場したindexがiの色の数

"""

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

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

c = list(map(int,input().split()))
last = [1] * (N+1)

li = [ [] for i in range(N+2)]
ans = [None] * Q
for i in range(Q):
    L,R = map(int,input().split())
    L += 1
    R += 1
    li[R].append((L,i))

BIT = [0] * (N+2)
bitadd(1,N,BIT)

for i in range(N):

    nc = c[i]
    lastind = last[nc]
    last[nc] = i+2

    bitadd(lastind,-1,BIT)
    bitadd(i+2,1,BIT)

    for l,qind in li[i+2]:
        ans[qind] = bitsum(i+2,BIT) - bitsum(l-1,BIT)

for i in ans:
    print (i)



### FIXED CODE ###


def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

from sys import stdin
N,Q = map(int,stdin.readline().split())

c = list(map(int,stdin.readline().split()))
last = [1] * (N+1)

li = [ [] for i in range(N+2)]
ans = [None] * Q
for i in range(Q):
    L,R = map(int,stdin.readline().split())
    L += 1
    R += 1
    li[R].append((L,i))

BIT = [0] * (N+2)
bitadd(1,N,BIT)

for i in range(N):

    nc = c[i]
    lastind = last[nc]
    last[nc] = i+2

    bitadd(lastind,-1,BIT)
    bitadd(i+2,1,BIT)

    for l,qind in li[i+2]:
        ans[qind] = bitsum(i+2,BIT) - bitsum(l-1,BIT)

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

N,D,A = map(int,input().split())
import numpy as np
import math
XH = [list(map(int,input().split())) for _ in range(N)]
XH = sorted(XH)
ans = 0
l=[0]*N
x = XH[0][0]
j = 0
while True:
  if j+1>=N:
    break
  if XH[j+1][0]<=x+2*D:
    j+=1
  else:
    break
l[0]=j
for i in range(1,N):
  x = XH[i][0]
  j = l[i-1]
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  l[i]=j
H = np.array([xh[1] for xh in XH])
for i,a in enumerate(l):
  h = H[i]
  if h<=0:
    continue
  else:
    b = math.ceil(h/A)
    ans += b
    H[i:a+1:]-=b*A
print(ans)

### FIXED CODE ###

def main():
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  S = [0]*(N+1)
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  b = (h+A-1)//A
  ans += b
  y = b*A
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  S[0]+=y
  S[j+1]-=y
  S[1]+=S[0]
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    s = S[i]
    rec = h-s
    if rec<=0:
      S[i+1]+=s
      continue
    else:
      x = xh[0]
      j = max(j,i)
      while True:
        if j+1>=N:
          break
        if XH[j+1][0]<=x+2*D:
          j+=1
        else:
          break
      b = (rec+A-1)//A
      ans += b
      y = b*A
      S[i]+=y
      S[j+1]-=y
      S[i+1]+=s+y
  print(ans)
main()
### BUGGY CODE ###

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


from functools import reduce

n = int(input())
a_s = list(map(int, input().split()))
mx = 0
for i in range(n):
    b = a_s[:i] + a_s[i + 1:]
    g = reduce(gcd, b)
    if g > mx:
        mx = g
print(mx)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def Lgcd(i):
    if i == 0:
        return 0
    if i == 1:
        return a_s[0]
    if i in Lmemo:
        return Lmemo[i]
    re = gcd(Lgcd(i - 1), a_s[i - 1])
    Lmemo[i] = re
    return re


def Rgcd(i):
    if i == n - 1:
        return 0
    if i == n - 2:
        return a_s[-1]
    if i in Rmemo:
        return Rmemo[i]
    re = gcd(Rgcd(i + 1), a_s[i + 1])
    Rmemo[i] = re
    return re


def gcd(a, b):
    if a * b == 0:
        return a + b
    while 1:
        a, b = b, a % b
        if b == 0:
            return a


Lmemo = {}
Rmemo = {}
n = int(input())
a_s = list(map(int, input().split()))
mx = 0
for i in range(n):
    g = gcd(Lgcd(i),Rgcd(i))
    if g > mx:
        mx = g
print(mx)
### BUGGY CODE ###

h, n = map(int, input().split())
a_list = []
b_list = []

for _ in range(n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

max_a = max(a_list)    
dp = [float('inf')] * (h + max_a + 1)

dp[0] = 0
for i in range(h):
    for j in range(n):
        dp[i + a_list[j]] = min(dp[i] + b_list[j], dp[i + a_list[j]])
print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
a_list = []
b_list = []

for _ in range(n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

max_a = max(a_list)    
dp = [float('inf')] * (h + max_a + 1)

dp[0] = 0
for i in range(h):
    for j in range(n):
        dp[i + a_list[j]] = min(dp[i] + b_list[j], dp[i + a_list[j]])
print(min(dp[h:]))
### BUGGY CODE ###

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

for i in range(10**19):
  n -= k
  if n <= 0:
    break
    
print(min(abs(n),n+k))

### FIXED CODE ###

n,k = map(int,input().split())
m = n//k
a = n - (k*m)
    
print(min(a,abs(a-k)))
### BUGGY CODE ###

from functools import reduce
from fractions import gcd

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

gcd_all = reduce(gcd, A)

for i in range(N):
    gcd_1 = reduce(gcd, (A[:i]+A[i+1:]))
    if gcd_1 >= gcd_all:
        gcd_all = gcd_1

print(gcd_all)


### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

L = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

max_m = 0
for i in range(N):
    m = gcd(L[i], R[i+1])
    if max_m < m:
        max_m = m
print(max_m)
### BUGGY CODE ###

n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]
count=0
for i in t:
    if i in s:
        count+=1

print(count)


### FIXED CODE ###

def search(L,e):
    """Lは昇順"""
    def bsearch(L,e,low,high):
        if high == low:
            return L[low] == e
        mid = (low + high)//2
        if L[mid] == e:
            return True
        elif L[mid] > e:
            if low==mid:
                return False
            else:
                return bsearch(L,e,low,mid-1)
        else:
            return bsearch(L,e,mid+1,high)
    if len(L) == 0:
        return False
    else:
        return bsearch(L,e,0,len(L)-1)
        
n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]
count=0
for i in t:
    if search(s,i):
        count+=1

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

class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            for a in tree:
                if y == a.id:
                    if a.k == 0:
                        a.type = 'leaf'
                    else:
                        a.type = 'internal node'
                    a.parent = x.id
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i


def setd(tree,node,d):
    node.depth = d
    if len(node.children) == 0:
        return
    else:
        for tmp in node.children:
            for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))

    

### FIXED CODE ###

class Node:
    def __init__(self, x, y):
        self.id = x
        self.k = y
        self.children = []
        self.type = ''
        self.depth = 20
        self.parent = '-1'

def findRoot(tree):
    for x in tree:
        for y in x.children:
            tree[int(y)].parent = x.id
            if tree[int(y)].k == 0:
                tree[int(y)].type = 'leaf'
            else:
                tree[int(y)].type = 'internal node'
            '''for a in tree:
                if y == a.id:
                    if a.k == 0:
                        a.type = 'leaf'
                    else:
                        a.type = 'internal node'
                    a.parent = x.id
            '''
    for i,x in enumerate( tree):
        if x.type == 'root':
            return i


def setd(tree,node,d):
    node.depth = d
    if node.k == 0:
        return
    else:
        for tmp in node.children:
            setd(tree,tree[int(tmp)],d+1)
            '''for x in tree:
                if x.id == tmp:
                    setd(tree,x,d+1)
            '''


if __name__ == '__main__':
    n = (int)(input())
    tree = [None]*n
    for i in range(0,n):
        tmp = input().split()
        a = Node(tmp[0],(int)(tmp[1]))
        a.children=tmp[2:]
        a.type = 'root'
        tree[int(a.id)] = a
    ri = findRoot(tree)
    setd(tree,tree[ri],0)
    
    for tmp in tree:
        print("node {}: parent = {}, depth = {}, {}, {}".format(tmp.id, tmp.parent,tmp.depth,tmp.type,list(map(int,tmp.children))))
### BUGGY CODE ###

N, M = map(int,input().split())
CardList = sorted(list(map(int,input().split())))
#print(CardList)
for _ in range(M):
  B, C = map(int,input().split())
  for i in range(B):
    if C > CardList[i]:
      CardList[i] = C
  CardList = sorted(CardList)
  
print(sum(CardList))

### FIXED CODE ###

n,m = map(int, input().split())
List = list(map(int, input().split()))
List.sort()
cand = []
for _ in range(m):
  b,c = map(int,input().split())
  cand.append((b,c))
bc = sorted(cand, key=lambda x: x[1], reverse=True)
i = 0
for b, c in bc:
    while b:
        if i < n and List[i] < c:
            List[i] = c
            b -= 1
        else:
            break
        i += 1
print(sum(List))
### BUGGY CODE ###

def solve(remains, nums):
    if (len(remains)) == 0:
        [print(num) for num in nums[::-1]]
        exit()
    n_remains = []
    n_nums = []
    for i, num in enumerate(remains):
        if i + 1 == num:
            n_remains.append(remains[:i] + remains[i + 1:])
            n_nums.append(nums + [i + 1])
    if len(n_remains) == 0:
        return False
    for n_remain, n_num in zip(n_remains, n_nums):
        solve(n_remain, n_num)


n = int(input())
B = [int(x) for x in input().split()]

solve(B, [])
print(-1)


### FIXED CODE ###

def solve(remains, nums):
    if (len(remains)) == 0:
        [print(num) for num in nums[::-1]]
        exit()
    n_remain = None
    n_num = None
    for i, num in enumerate(remains):
        if i + 1 == num:
            n_remain = remains[:i] + remains[i + 1:]
            n_num = nums + [i + 1]
    if n_remain is None:
        return False
    solve(n_remain, n_num)


n = int(input())
B = [int(x) for x in input().split()]

solve(B, [])
print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(len(a)):
    for j in a:
        if i+1 == j:
            ans.append(a.index(j)+1)
print(*ans)


### FIXED CODE ###

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

n=int(input())
b=[0]
for i in range(n):
    b.append(int(input()))
x=1
r=[0]
while 1:
    i=b[x]
    if i==2:
        print(len(r))
        break
    elif i in r:
        print(-1)
        break
    x=i
    r.append(i)

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):a.append(int(input()))
x=1
for i in range(n):
    x=a[x-1]
    if x==2:
        print(i+1)
        break
else:print(-1)
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//1000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())

        a -= 1
        base[a] += v

        b = a - a % 1000
        value = base[b]
        index = b
        end = b + 1000 if b + 1000 < n else n
        for i in range(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//1000] = index

        index = midway[0]
        value = base[index]
        for i in midway:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//100 + 1)
    last = [0] * (n//10000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())

        a -= 1
        base[a] += v

        b = a - a % 100

        index = b
        value = base[b]
        end = b + 100 if b + 100 < n else n
        for i in range(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//100] = index

        c = a - a % 10000
        cc = c // 100

        index = c
        value = base[c]
        for i in midway[cc:cc+100]:
            if value < base[i]:
                value = base[i]
                index = i
        last[c//10000] = index

        index = last[0]
        value = base[index]
        for i in last:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


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

import bisect
N = int(input())
A_arr = list(map(int,input().split()))
A_arr.sort()
B_arr = list(map(int,input().split()))
B_arr.sort()
C_arr = list(map(int,input().split()))
C_arr.sort()
ans = 0
for i in C_arr:
    B_index = bisect.bisect_left(B_arr,i)
    for k in range(B_index):
        ans += bisect.bisect_left(A_arr,B_arr[k])
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A_arr = list(map(int,input().split()))
A_arr.sort()
B_arr = list(map(int,input().split()))
B_arr.sort()
C_arr = list(map(int,input().split()))
ans = 0
check_array = [0] * N
for i in range(N):
    check_array[i] = check_array[i-1]+bisect.bisect_left(A_arr,B_arr[i])
for i in C_arr:
    B_index = bisect.bisect_left(B_arr,i)
    if B_index == 0:
        continue
    ans += check_array[B_index-1]
print(ans)
### BUGGY CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

### FIXED CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

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

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    chance = [i for i in range(N)]
    flag  = [True] * N #試合をしたかどうかチェック
    while len(chance) != 0: # and tmp < 2 * N + 2:
        ans += 1
        flag  = [True] * N #試合をしたかどうかチェック
        tmp_lst = []
        # print ('chance', chance)
        for i in chance:
            if check[i] >= N - 1 or flag[i] == False:
                # tmp += 1
                continue
            b = A[i][check[i]] - 1
            # print (b)
            if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
                check[i] += 1
                check[b] += 1
                flag[i] = False
                flag[b] = False
                # tmp = 0
                count += 1
                tmp_lst.append(i)
                tmp_lst.append(b)
                if count == (N * (N - 1))//2:
                    print (ans)
                    exit()
        chance = tmp_lst
    print (-1)
    return 
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

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

a_set = set(a_list)
a_set_len = len(a_set)
a_count = sorted([a_list.count(i) for i in a_set])

count = 0
for i in range(max((a_set_len - k), 0)):
    count += a_count[i]

print(count)

### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a_list = list(map(int, input().split()))

counter = Counter(a_list).most_common()[::-1]

count = 0
for i in range(max((len(counter) - k), 0)):
    count += counter[i][1]

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-06-26 20:59:48 +0900
# LastModified: 2020-06-26 21:19:42 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    expected = list(map(lambda x: (x+1)/2, p))
    e_max = 0
    for i in range(n-(k-1)):
        a = sum(expected[i:i+k])
        if e_max<a:
            e_max=a
    print(e_max)
    



if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-07-29 16:20:16 +0900
# LastModified: 2020-07-29 16:30:22 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from itertools import accumulate


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    s = [(x+1)/2 for x in p]
#    print(s)
    s = list(accumulate(s))
    s.insert(0, 0)
    ans = 0
#    print(s)
    for i in range(n-k+1):
        ans = max(ans, s[i+k]-s[i])
    print(ans)



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

class Graph:
    def __init__(self, V, directed=False):
        self.V = V
        self.directed = directed
        self.adj_list = {i: [] for i in self.V}
        
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        if not self.directed:
            self.adj_list[v].append(u)

def bipartite(graph):
    color = {v: None for v in graph.V}
    stack = [(graph.V[0], 0)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for u in graph.adj_list[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    parts = {0: [], 1:[]}
    for v in graph.V:
        parts[color[v]].append(v)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
g = Graph(range(1, N+1))
for _ in range(M):
    a, b = map(int, input().split())
    g.add_edge(a, b)
p1, p2 = bipartite(g)
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)

### FIXED CODE ###

def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: [], 1:[]}
    while stack:
        v, c = stack.pop()
        if color[v] is not None: # consistent
            continue
        color[v] = c
        parts[c].append(v)
        for u in E[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
V = range(1, N+1)
E = {v: [] for v in V}
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)