Harryxun/stf_run huggingface dataset:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

import copy
N = int(input())
A = [0] * N
for i in range(N):
  a, b = map(int, input().split())
  A[i] = [i, a, b]

B = copy.deepcopy(A)  
A = sorted(A, key = lambda x:x[1])
B = sorted(B, key = lambda x:x[2])
#print(A, B)

data = UnionFind(N + 1)
a, b = 1, 1
cost = 0
for i in range(N):
  #print(a, b, cost)
  one = abs(A[a][1] - A[a - 1][1])
  two = abs(B[b][2] - B[b - 1][2])
  if one > two:
    if not data.same_check(B[b][0], B[b - 1][0]):
      data.union(B[b][0], B[b - 1][0])
      cost += two
    b += 1
    
  else:
    if not data.same_check(A[a][0], A[a - 1][0]):
      data.union(A[a][0], A[a - 1][0])
      cost += one     
    a += 1
  
print(cost)  
  
  

  

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

import copy
N = int(input())
A = [0] * N
for i in range(N):
  a, b = map(int, input().split())
  A[i] = [i, a, b]

B = copy.deepcopy(A)  
A = sorted(A, key = lambda x:x[1])
B = sorted(B, key = lambda x:x[2])
#print(A, B)

#それぞれの辺のながさを求めて、小さい順にする
#[点の番号、点の番号、２点間距離]
A2 = [0] * (N - 1)
for i in range(1, N):
  l = abs(A[i][1] - A[i - 1][1])
  A2[i - 1] = [A[i][0], A[i - 1][0], l]

B2 = [0] * (N - 1)
for i in range(1, N):
  l = abs(B[i][2] - B[i - 1][2])
  B2[i - 1] = [B[i][0], B[i - 1][0], l]  
Len = A2 + B2
Len = sorted(Len, key = lambda x:x[2])
#print(Len)

data = UnionFind(N + 1)
cost = 0
for i in range(len(Len)):
    if not data.same_check(Len[i][0], Len[i][1]):
      data.union(Len[i][0], Len[i][1])
      cost += Len[i][2]

  
print(cost)
n = int(input())
a = list(map(int, input().split()))
if n == 1:
    print(1)
    exit()

a.sort()
li = []
count = 1
for i in range(n-1):
    if a[i] == a[i+1]:
        count += 1
    else:
        li.append(count)
        count = 1

li.sort()
count2 = 0
for i in range(len(li)-2):
    x = li[i] + li[i+1] + li[i+2]
    if x >= count2:
        count2 = x

print(x)



### FIXED CODE ###

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

t = max(a)
num_list = [0] * (t + 2)

for i in range(n):
    num_list[a[i]] += 1
    if a[i] == 0:
        continue
    else:
        num_list[a[i]-1] += 1
    if a[i] == t:
        continue
    else:
        num_list[a[i]+1] += 1

print(max(num_list))
input();a=map(int,input().split());print(max(a)-min(a))

### FIXED CODE ###

input();a=list(map(int,input().split()));print(max(a)-min(a))
n = int(input())
if n[0] == n[1] and n[1] == n[2]:
  print('Yes')
elif n[1] == n[2] and n[2] == n[3]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = input()

if (n[0] == n[1]) and (n[1] == n[2]):
  print('Yes')
elif (n[1] == n[2]) and (n[2] == n[3]):
  print('Yes')
else:
  print('No')
def cin():  return list(map(int,input().split()))

N, M, Q = list(map(int,input().split()))
v = [[0 for _ in range(N)] for _ in range(N)]
p = [[0 for _ in range(2)] for _ in range(N)]

for i in range(M):
    a, b = cin()
    v[a - 1][b - 1] += 1;

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;
    
def d2_add(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

def d2_calc(da, p, q, x, y):
    if p > x or q > y:  return 0
    if p == 0 and q == 0:  return da[x][y]
    if p == 0:  return da[x][y] - da[x][q - 1]
    if q == 0:  return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

ret = d2_add(v)
for i in range(Q):
    ans = d2_calc(ret, p[i][0], p[i][0], p[i][1], p[i][1])
    print(ans)

### FIXED CODE ###

N, M, Q = list(map(int,input().split()))
L = []
R = []
for i in range(M):
    in1, in2 = map(int,input().split())
    L.append(in1 - 1)
    R.append(in2 - 1)
p = []
q = []
for i in range(Q):
    in1, in2 = map(int,input().split())
    p.append(in1 - 1)
    q.append(in2 - 1)
    
a = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    a[L[i]][R[i]] += 1
    
#da[i][j]:(0,0)~(i,j)の長方形の和
def da_gen(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(da, p, q, x, y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y] - da[x][q - 1]
    if q == 0:
        return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1]+da[p - 1][q - 1]

ret = da_gen(a)
for i in range(Q):
    ans = da_calc(ret, p[i], p[i], q[i], q[i])
    print(ans)
import collections 

n = int(input())
input_list = [int(i) for i in input().split(' ')]

counter = collections.Counter(input_list)


unique_list = list(counter.keys())
counts = list(counter.values())

if (all(num == 0 for num in unique_list)):
    print('Yes')
else:
    if len(counter) != 3:
        print('No')
    if (unique_list[0] ^ unique_list[1] == unique_list[2]):
        if (all(counts[0] == num for num in counts)):
            print('Yes')
    print('No')

### FIXED CODE ###

import collections 

n = int(input())
input_list = [int(i) for i in input().split(' ')]

counter = collections.Counter(input_list)


unique_list = list(counter.keys())
counts = list(counter.values())

if (all(num == 0 for num in unique_list)):
    print('Yes')
else:
    if n % 3 == 0:
        zero_count = counter[0] 
        if zero_count == n / 3 and len(unique_list) == 2:
            print('Yes')
        else: 
            if len(unique_list) != 3:
                print('No')
            elif (unique_list[0] ^ unique_list[1] == unique_list[2]):
                if (all(counts[0] == num for num in counts)):
                    print('Yes')
                else:
                    print('No')
            else:
                print('No')
    else:
        print('No')
N,M = map(int,input().split())
dict = {}
for m in range(M):
    a,b = map(int,input().split())
    if a in dict:
        dict[a].append(b)
    else:
        dict[a] = [b]
    if b in dict:
        dict[b].append(a)
    else:
        dict[b] = [a]
ans = 0
l = [0 for i in range(N+1)]
l[1] = 1
def dfs(now):
    global l
    global ans
    if sum(l) == N:
        ans += 1
        return(0)
    for i in dict[now]:
        if l[i] == 0:
            l[i] += 1
            now = i
            dfs(l,now)
            l[i] -= 1
        else:
            continue
dfs(l,1)
print(ans)


### FIXED CODE ###

N,M = map(int,input().split())
dict = {}
for m in range(M):
    a,b = map(int,input().split())
    if a in dict:
        dict[a].append(b)
    else:
        dict[a] = [b]
    if b in dict:
        dict[b].append(a)
    else:
        dict[b] = [a]
ans = 0
l = [0 for i in range(N+1)]
l[1] = 1
def dfs(l,now):
    global ans
    if sum(l) == N:
        ans += 1
        return(0)
    for i in dict[now]:
        if l[i] == 0:
            l[i] += 1
            now = i
            dfs(l,now)
            l[i] -= 1
        else:
            continue
dfs(l,1)
print(ans)
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = 0

for i in range(n):
	if a[i] >= b[i]:
		c += b[i]
	else:
		c += a[i]
		c += min(a[i+1],b[i]-a[i])
		if a[i+1] >= b[i]-a[i]
			a[i+1] = a[i+1] - (b[i] - a[i])
		else:
			a[i+1] = 0
print(c)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = 0
 
for i in range(n):
  if a[i] >= b[i]:
    c += b[i]
  else:
    c += a[i]
    c += min(a[i+1],b[i]-a[i])
    if a[i+1] >= b[i]-a[i]:
      a[i+1] = a[i+1] - (b[i] - a[i])
    else:
      a[i+1] = 0
     
print(c)
import sys
import numpy as np
import collections
r = [0]*100000
n,k = [int(x) for x in sys.stdin.readline().split()]
for i in range(n):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	r[a] += b
c = 0
for i,j in enumerate(r):
	c += j
	if c >= k:
		print(i)
		break

### FIXED CODE ###

import sys
import numpy as np
import collections
n,k = [int(x) for x in sys.stdin.readline().split()]
r = collections.defaultdict(int)
for i in range(n):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	r[a] += b
d = sorted(r.items())
c = 0
for i,j in enumerate(d):
	c += j[1]
	if c >= k:
		print(int(j[0]))
		break
input = int(input())
 
hour = input // 3600
minute = input - 3600 * hour
second = hour - 60 * minute
 
print(str( hour : minute : second ))

### FIXED CODE ###

sec_ = int(input())
print("{}:{}:{}".format(sec_//3600, (sec_//60)%60, sec_%60))
a = int(input())
b = int(input())
if a*b%2==0:
    print('Even')
else:
    print('Odd')


### FIXED CODE ###

a = list(map(int, input().split()))
if a[0]*a[1]%2==0:
    print('Even')
else:
    print('Odd')
import sys

S = [int(i) for i in input().split()]
T = sum(T)/2

for i in range(3):
  if S[i] == T:
    print("Yes")
    sys.exit()
    
print("No")

### FIXED CODE ###

import sys

S = [int(i) for i in input().split()]
T = sum(S)/2

for i in range(3):
  if S[i] == T:
    print("Yes")
    sys.exit()
    
print("No")
import math
import sys

n = input()
a = list(map(int, input().split()))
b = sorted(a)
c = set(b)
if len(c) == 1:
  print(c[0])
  sys.exit()
pl = []
ql = []
for i in b[1:]:
  pl.append(math.gcd(b[0], i))
for i in b[2:]:
  ql.append(math.gcd(b[1], i))
pls = sorted(pl)
qls = sorted(ql)
if len(qls) == 0:
  print(pls[min(1, len(pls) - 1)])
else:
  print(max(pls[min(1, len(pls) - 1)], qls[0]))

### FIXED CODE ###

import math
import itertools

n = int(input())
a = list(map(int, input().split()))
pf = [0]*(n+1)
pb = [0]*(n+1)
p = a[0]
for i in range(n):
  p = math.gcd(p, a[i])
  pf[i+1] = p
p = a[-1]
for i in range(-1, -n-1, -1):
  p = math.gcd(p, a[i])
  pb[i-1] = p
ans = [0]*n
for i in range(n):
  ans[i] = math.gcd(pf[i], pb[i+1])
print(max(ans))
from collections import deque

n = int(input())
commands = [input().split() for _ in range(n)]

l = deque([])
for com in commands:
    if com[0]=='insert':
        l.insert(0, com[1])
    elif com[0]=='delete':
        try:
            l.remove(com[1])
        except:
            pass
    elif com[0]=='deleteFirst':
        l.pop(0)
    elif com[0]=='deleteLast':
        l.pop()
s = ' '.join(l)
print(s)


### FIXED CODE ###

from collections import deque

n = int(input())
commands = [input() for _ in range(n)] # splitとかしてると間に合わない

l = deque()
for com in commands:
    if com[0]=='i':
        l.appendleft(com[7:])
    elif com[6]=='F':
        l.popleft()
    elif com[6]=='L':
        l.pop()
    else:
        try:
            l.remove(com[7:])
        except:
            pass

s = ' '.join(l)
print(s)
import sys
S = input().strip()
keyence = "keyence"

for i in range(len(keyence)):
    if keyence[:i] in S:
        s = S.find(keyence[:i]) + i
        S2 = S[s:]
        if keyence[i:] in S2:
            print("YES")
            sys.exit()

print("NO")
~           

### FIXED CODE ###

import sys
S = input().strip()
keyence = "keyence"
n = len(keyence)

if keyence in S:
    k = S.find(keyence)
    if k == 0:
        print("YES")
        sys.exit()
    elif k + n == len(S):
        print("YES")
        sys.exit()

for i in range(n):
    if S[:i] == keyence[:i] and S[-(n-i):] == keyence[-(n-i):]:
        print("YES")
        sys.exit()

print("NO")
s = input()
for i in len(s):
  print(x,end="")


### FIXED CODE ###

s = input()
print("x" * len(s))
M,N,K = map(int,input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
m = 0
c = 0
while True:
    if len(A) == 0:
        r = B.pop(0)
    elif len(B) == 0:
        r = A.Pop(0)
    elif A[0] > B[0]:
        r = B.pop(0)
    else:
        r = A.pop(0)
    if m+r > K:
        break
    c += 1
    m += r
    if m+r >= K:
        break
print(c)


### FIXED CODE ###

N,M,K = map(int,input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
AA = [0]
BB = [0]
r = 0
for i in A:
    r += i
    AA.append(r)
r = 0
for i in B:
    r += i
    BB.append(r)
ans = 0
a = N
b = 0
while AA[a]+BB[b] > K:
    a -= 1
ans = a+b

while a >= 0:
    while b < M:
        if AA[a]+BB[b+1] <= K:
            b += 1
        else:
            break
    if ans < a+b:
        ans = a+b
    if b == M:
        break
    a -= 1
print(ans)
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=check[n]+n*d,check[0]
    if n//ttf in check:
        if check[n//ttf]>check[n]+(n%ttf)*d+cha:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    else:
        check[n//ttf]=check[n]+(n%ttf)*d+cha
        dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
N = input()

S = N*(N+1)/2

print(S)

### FIXED CODE ###

N = int(input())

S = N*(N+1)//2

print(S)
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda l:(l[0]))
c=0
used=[]
def find_num(itr,target):
    for j in range(itr, m):
        if target in l[j]:
            next_target=[k for k in l[j] if k!=target][0]
            used.append(next_target)
            if len(used) == n:
                return True
            if find_num(j,next_target):
                return True
            else:
                return False
    return False

for i in range(m):
    used=[]
    if 1 in l[i]:
        used.append(1)
        next_target = [k for k in l[i] if k != 1][0]
        used.append(next_target)
        rtn=find_num(i, next_target)
        if rtn:
            c+=1
print(c)


### FIXED CODE ###

import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)
n=int(input())
if(n==25):
  print("Christmas")
elif(n=24):
  print("Christmas Eve")
elif(n=23):
  print("Christmas Eve Eve")
elif(n==22):
  print("Christmas Eve Eve Eve")

### FIXED CODE ###

n=int(input())
if(n==25):
  print("Christmas")
elif(n==24):
  print("Christmas Eve")
elif(n==23):
  print("Christmas Eve Eve")
elif(n==22):
  print("Christmas Eve Eve Eve")
import math
X, Y = map(int,input().split())
a=(-X+2*Y)/3
b=(2*X-Y)/3
if a.is_integer()==False or b.is_integer()==False:
    print(0)
else:
    print(math.factorial(int(a+b)) // (math.factorial(int(a)) * math.factorial(int(b))))

### FIXED CODE ###

p = 1000000007

X, Y = map(int, input().split())

if (X + Y) % 3 != 0:
    print(0)
    exit()

a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

if a < 0 or b < 0:
    print(0)
    exit()

n = a + b
fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % p


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


print(mcomb(n, a))
#他者の解答を参考にした
import math
a,b,c,d = map(int,input().split())
li=[]
for i in [a-1,b]:
    bc = i//c
    bd = i//d
    gcd = c*d / math.gcd(c,d)
    cd = i//gcd
    li.append(i-(bc+bd-cd))
print(int(li[1]-li[0]))

### FIXED CODE ###

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

a,b,c,d = map(int,input().split())
li=[]
gc = lcm(c,d)
for i in [a-1,b]:
    bc = i//c
    bd = i//d
    cd = i//gc
    li.append(i-(bc+bd-cd))
print(int(li[1]-li[0]))
h,w = map(int,input().split())
maps = []

for i in range(h):
    maps.append(list(map(int,input().split())))
for i in range(h):
    for j in range(w):
        if maps[i][j] == "snuke":
            print(i+1)
            exit()

### FIXED CODE ###

h,w = map(int,input().split())
maps = []
alphabet = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
for i in range(h):
    maps.append(list(map(str,input().split())))
for i in range(h):
    for j in range(w):
        if maps[i][j] == "snuke":
            print(alphabet[j]+str(i+1))
            exit()
import sys
import  math
import fractions
from collections import defaultdict
import heapq
from bisect import bisect_left,bisect

stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K=nm()
A=nl()
l=1
r=10**9
mid=0

if(K==0):
    print(max(A))
    sys.exit(0)

while(l+1<r):
    mid=(l+r)//2
    tmp=0
    for i in range(len(A)):
        tmp+=A[i]//mid
    if(K<tmp):
        l=mid
    else:
        r=mid

tmp=0
for i in range(len(A)):
    tmp+=A[i]//l

tmp2=0
for i in range(len(A)):
    tmp2+=A[i]//(l-1)



if(tmp2<=K):
    print(l-1)
    sys.exit(0)

if(tmp<=K):
    print(l)
    sys.exit(0)

print(r)




    

### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
import heapq
from bisect import bisect_left,bisect

stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K=nm()
A=nl()
l=0
r=10**9
mid=0

if(K==0):
    print(max(A))
    sys.exit(0)

while(l+1<r):
    mid=(l+r)//2
    tmp=0
    for i in range(len(A)):
        tmp+=((A[i]-1)//mid)
    if(tmp<=K):
        r=mid
    else:
        l=mid

print(r)
import numpy as np

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    # list of expected value
    e = [(p[j-1]+1)/2.for j in range(1, n+1)]
    # cumulative sum for e
    c_s = np.cumsum(e)
    # sum of range k
    s = c_s[k:] - c_s[:n-k]
    # calculate max of s
    ans = max(s)

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    e = [(p[j-1]+1)/2.for j in range(1, n+1)]
    s = [sum(e[:k])]
    for i in range(1, n-k+1):
        s.append(s[-1]-e[i-1]+e[k+i-1])
    ans = max(s)
    print(ans)

if __name__ == "__main__":
    main()
#!/usr/bin/env python3
import sys
import math


def solve(A: int, B: int):
    # al = make_divisors(A)
    # bl = make_divisors(B)
    # l = sorted(al & bl)
    gcd = math.gcd(A, B)
    f = factorize(gcd)
    print(1 + len(f))


def factorize(n: int):
    res = []
    end = int(n ** 0.5//1 + 2)
    for i in range(2, end):
        if n % i:
            continue
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        res.append([i, s])
    return res


# 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


# Generated by 1.1.5 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()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import math

def solve(A: int, B: int):
    # math.gcd()は3.5から
    # g = math.gcd(A, B)
    g = gcd(A, B)
    f = factorize(g)
    print(1 + len(f))


def gcd(x: int, y: int):
    return gcd(y, x % y) if y else x


def factorize(n: int):
    res = []
    for i in range(2, int(n ** 0.5//1 + 2)):
        if n % i:
            continue
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        res.append([i, s])
    if n != 1:
        res.append([n, 1])
    return res


# Generated by 1.1.5 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()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = [0] * w
for i in range(1, n + 1):
    for j in range(w):
        if wv[i - 1][0] <= j:
            l[i][j] = max(l[i - 1][j], l[i - 1][j - wv[i - 1][0]] + wv[i - 1][1])
        else:
            l[i][j] = l[i - 1][j]
print(l[n][w - 1])

### FIXED CODE ###

n, w = map(int, input().split())
l1 = [list(map(int, input().split())) for i in range(n)]
v = 0
for i in range(n):
  v += l1[i][1]
d = [10 ** 9 + 1] * (v + 1)
d[0] = 0
for i in range(n):
    for j in range(v, -1, -1):
        d[j] = min(d[j], d[j - l1[i][1]] + l1[i][0])
answer = 0
for j in range(v + 1):
    if  w >= d[j]:
        answer = max(answer, j)
print(answer)