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

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
d = {}
py = []
for i in range(1,m+1):
    p,y = map(int, input().split())
    py.append((p,y))
    if p not in d:
        d[p] = []
    d[p].append([y,i])

for k in d.keys():
    d[k] = sorted(d[k])

for p,y in py:
    idx = 0
    for i in range(len(d[p])):
        if d[p][i][0]==y:
            idx = i+1
            break
    print("{:06}{:06}".format(p,idx))


### FIXED CODE ###

# -*- coding: utf-8 -*-

n,m = map(int, input().split())
d = {}
py = []
for i in range(1,m+1):
    p,y = map(int, input().split())
    py.append((p,y))
    if p not in d:
        d[p] = []
    d[p].append([y,i])

ret = {}
for k in d.keys():
    d[k] = sorted(d[k])
    ret[k] = {}
    for i in range(len(d[k])):
        ret[k][d[k][i][0]] = i+1

for p,y in py:
    print("{:06}{:06}".format(p,ret[p][y]))
### BUGGY CODE ###

ks= list(map(int, input().split())) 
 
count = 0
 
x = 0
y = 0
z = 0
 
for targetX in range(ks[0]+1):
    
    
    if targetX <= ks[0] and ks[1]-(targetX+ks[0]+ks[0]) <= 0:
    
        for targetY in range(ks[0]+1):
            
            z = ks[1] - (targetX + targetY)
            
            if 0 <= z and z <= ks[0]:
                count += 1
                
        
            targetY +=1
        
    targetX +=1
        
 
print(count)

### FIXED CODE ###

ks= list(map(int, input().split())) 
 
count = 0
 
x = 0
y = 0
z = 0
 
for targetX in range(ks[0]+1):
    
    
    if targetX <= ks[0] and ks[1]-(targetX+ks[0]+ks[0]) <= 0:
    
        for targetY in range(ks[0]+1):
            
            z = ks[1] - (targetX + targetY)
            
            if 0 <= z and z <= ks[0]:
                count += 1
                
        
        
        
 
print(count)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=[]
def divis(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            a[i-1]^=1
            if i != n // i :
                ij=n//i
                a[ij-1]^=1
for i in reversed(range(n)):
    if a[i]==1:
        cnt.append(i+1)
        divis(i+1)
if len(cnt)>0:
    print(len(cnt))
    print(*cnt)
else:
    print(0)



### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=[]
def divis(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            a[i-1]^=1
            if i != n // i :
                ij=n//i
                a[ij-1]^=1
for i in reversed(range(n)):
    if a[i]==1:
        cnt.append(i+1)
        divis(i+1)
if len(cnt)>0:
    print(len(cnt))
    print(*cnt)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split()))
s = 0
mod = 10**9+7
for i in range(n-1):
    for j in range(i+1, n):
        s += arr[i]*arr[j]
print(s%mod)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
s = sum(arr)
s = s*s
mod = 10**9 + 7
ind = 0
for i in range(n):
    ind += arr[i]*arr[i]
print(((s-ind)//2)%mod)
### BUGGY CODE ###

import math
X,Y = list(map(int, input().split()))
cnts = [0,0]
while X>0 and Y>0:
    if X <= Y:
        cnts[1] += 1
        X -= 1
        Y -= 2
    else:
        cnts[0] += 1
        X -= 2
        Y -= 1
        
if X == 0 and Y == 0:
    i = cnts[0]
    j = cnts[1]
    print(math.factorial(i+j)//(math.factorial(i)*math.factorial(j)) % (10**9 + 7))
else:
    print(0)

### FIXED CODE ###


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

# X = 2n+m, Y = n+2mとして
n = (2*X-Y)//3
m = (Y-n)//2

mod = 10**9+7 #出力の制限
N = n+m
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


if (X + Y) % 3 != 0:
    print(0)
elif n < 0 or m < 0:
    print(0)
else:
    print(cmb(n+m, n, mod))
### BUGGY CODE ###

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

for i in range(n-k):
  pre = 1
  now = 1
  for j in range(k):
    pre *= A[i+j]
    now *= A[i+j+1]
  if pre < now:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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

for i in range(n-k):
    if A[i+k] > A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#bit全探索する
INF =  5000

N, Ma, Mb = map(int, input().split())
a, b, c = [], [], []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    a.append(Lst[0])
    b.append(Lst[1])
    c.append(Lst[2])

cost = INF
for n in range(1,2**N):
    A, B, C = 0, 0, 0
    for i in range(N):
        if n & (1<<i):
            A += a[i]
            B += b[i]
            C += c[i]
            if C > cost:
                break
    if A * Mb == B * Ma:
        cost = min(cost, C)
if cost != INF:
    print(cost)
else:
    print(-1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys

n,k = map(int, input().split())
td = []
td_mx = {}
for _ in range(n):
  t,d = map(int, input().split())
  td.append(d)
  if (t not in td_mx) or (td_mx[t] < d):
    td_mx[t] = d
td = sorted(td)
td_mx = sorted(td_mx.values())

mx_sum = 0
t_mx = len(td_mx)
ans = 0
for t in range(1, min(t_mx,k)+1):
  mx_sum += td_mx[-1]
  td.remove(td_mx[-1])
  td_mx.pop(-1)
  if t < k:
    ans = max(ans, mx_sum + sum(td[-k+t:]) + t**2)
  else:
    ans = max(ans, mx_sum + t**2)

print(ans)


### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys


n,k = map(int, input().split())
td_mx = {}
td = []
for _ in range(n):
  t,d = map(int, input().split())
  if t not in td_mx:
    td_mx[t] = d
  elif td_mx[t] < d:
    td.append(td_mx[t])
    td_mx[t] = d
  else:
    td.append(d)
td = sorted(td, key=lambda x:-x)
td_mx = sorted(td_mx.values(), key=lambda x:-x)

# td,td_mx の累積和を求める
csum = [0]
csum_mx = [0]
for i in range(len(td)):
  csum.append(csum[-1] + td[i])
for i in range(len(td_mx)):
  csum_mx.append(csum_mx[-1] + td_mx[i])


# 1~k種類で探索 最大値を取り出す
ans = 0
for i in range(1,k+1):
  if i <= len(csum_mx)-1 and k-i <= len(csum)-1:
    ans = max(ans, csum_mx[i] + csum[k-i] + i*i)
print(ans)
### BUGGY CODE ###

K,S = map(int,input().split(" "))
     
s = 0
     
for x in range(K+1):
  if x >S:
    break
  for y in range(K+1):
    if x + y >S:
      break
    for z in range(K+1):
      if x +y +z ==S:
        s +=1
      if x + y + z >S:
        break
     
print(s)

### FIXED CODE ###

K,S = map(int,input().split(" "))
             
s = 0
             
for x in range(K+1):
  for y in range(min(K+1,S-x+1)):
    if 0<=S-x - y <= K:
      s+=1
                     
print(s)
### BUGGY CODE ###

import itertools

N=int(input())
S=input()
a,b,c=0,0,0

l=set(itertools.combinations(S, 3))

print(len(l))

### FIXED CODE ###

N=int(input())
S=input()
cnt=0
 
for i in range(10):
    a=S.find(str(i))
    if a==-1:
        continue
    for j in range(10):
        b=S.find(str(j),a+1)
        if b==-1:
            continue
        for k in range(10):
            if S.find(str(k),b+1)!=-1:
                cnt+=1
print(cnt)
### BUGGY CODE ###

# B - RGB Boxes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
R,G,B,N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(N-r+1):
        t = N-(R*r+g*G)
        if t>=0 and t%B==0:
            ans += 1
print(ans)

### FIXED CODE ###

# B - RGB Boxes
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
R,G,B,N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(N-r+1):
        t = N-(R*r+g*G)
        if t>=0 and t%B==0:
            ans += 1
print(ans)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input())-1 for i in range(q)]
point=[k-(q-a.count(i)) for i in range(n)]
for i in point:
    print("Yes" if i>0 else "No")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input())-1 for i in range(q)]
point=[k-q for i in range(n)]
for i in a:
    point[i]+=1

for i in point:
    print("Yes" if i>0 else "No")
### BUGGY CODE ###

N = int(input())

for i in range(1,N+1):
    ans = 0

    for x in range(1,101):
        if x**2>i:
            break
        for y in range(1,101):
            if x**2+y**2>i:
                break
            for z in range(1,101):
                if x**2+y**2+z**2+x*y+y*z+z*x==i:
                    ans += 1
                
    print(ans)

### FIXED CODE ###

N = int(input())

for i in range(1,N+1):
    ans1 = 0
    ans2 = 0
    ans3 = 0
    
    for x in range(1,101):
        if x**2>i:
            break
        for y in range(1,x):
            if x**2+y**2+x*y>i:
                break
            for z in range(1,y):
                if x**2+y**2+z**2+x*y+y*z+z*x==i:
                    ans1 += 1

                if x**2+y**2+z**2+x*y+y*z+z*x>i:
                    break

    for x in range(1,101):
        if x**2>i:
            break
        for y in range(1,x):
            if x**2+y**2>i:
                break
            if x**2+3*y**2+2*x*y==i:
                ans2 += 1
    
    for x in range(1,101):
        if x**2>i:
            break
        for y in range(1,x):
            if x**2+y**2>i:
                break
            if 3*x**2+y**2+2*x*y==i:
                ans2 += 1
                
    for x in range(1,101):
        if 6*x**2==i:
            ans3+=1

    print(ans1*6+ans2*3+ans3)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

def main():
    h, w = map(int, input().split())
    mp = ["X" * (w + 2)] + ["X" + input() + "X" for _ in range(h)] + ["X" * (w + 2)]
    checked = [[False] * (w + 2) for _ in range(h + 2)]
    vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


    def search(x, y):
        checked[y][x] = True
        if mp[y][x] == "#":
            b_cnt = 1
            w_cnt = 0
            another = "."
        else:
            b_cnt = 0
            w_cnt = 1
            another = "#"
        for dx, dy in vec:
            nx, ny = x + dx, y + dy
            if not checked[ny][nx] and mp[ny][nx] == another:
                w_add, b_add = search(nx, ny)
                w_cnt += w_add
                b_cnt += b_add
        return w_cnt, b_cnt

    ans = 0
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if not checked[y][x]:
                w_cnt, b_cnt = search(x, y)
                ans += w_cnt * b_cnt

    print(ans)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def main():
    h, w = map(int, input().split())
    mp = ["X" * (w + 2)] + ["X" + input() + "X" for _ in range(h)] + ["X" * (w + 2)]
    checked = [[False] * (w + 2) for _ in range(h + 2)]
    vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


    def search(stack):
        x, y = stack.pop()
        if mp[y][x] == "#":
            b_cnt = 1
            w_cnt = 0
            another = "."
        else:
            b_cnt = 0
            w_cnt = 1
            another = "#"
        for dx, dy in vec:
            nx, ny = x + dx, y + dy
            if not checked[ny][nx] and mp[ny][nx] == another:
                checked[ny][nx] = True
                stack.append((nx, ny))
        return w_cnt, b_cnt

    ans = 0
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if not checked[y][x]:
                checked[y][x] = True
                stack = []
                stack.append((x, y))
                w_cnt = b_cnt = 0
                while stack:
                    w_add, b_add = search(stack)
                    w_cnt += w_add
                    b_cnt += b_add
                ans += w_cnt * b_cnt

    print(ans)

main()
### BUGGY CODE ###

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

c = 0


for i in range(0, n//(a+b)):
    c = a * (n//(a+b))

if n%(a+b) > a:
    c += a
else:
    c += n%(a+b)
    
print(c)

### FIXED CODE ###

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

cycles = n//(a+b)
count = 0
count += a*cycles
rest = n - (a+b)*cycles
if rest > a:
    count += a
else:
    count += rest
print(count)
### BUGGY CODE ###

import sys
from heapq import heappush, heappop

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

g2 = [[] for _ in range(n + 1)]
e = set()
hq = []
for u in range(1, n+1):
    for v in g[u]:
        heappush(hq, (1, u, v))

while hq:
    dux = heappop(hq)
    if dux in e:
        continue
    e.add(dux)
    d, u, x = dux
    if d == 3:
        g2[u].append(x)
        continue
    for y in g[x]:
        heappush(hq, (d+1, u, y))

def main():
    hq = [(0, s)]
    dist = [inf] * (n + 1)
    while hq:
        d, x = heappop(hq)
        if dist[x] != inf:
            continue
        dist[x] = d
        for y in g2[x]:
            if dist[y] == inf:
                heappush(hq, (d+1, y))
    
    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys
from heapq import heappush,heappop

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

def main():
    dist = [inf] * (n + 1)
    can_reach = [[False] * 3 for _ in range(n + 1)]
    hq = [(0, s)]
    can_reach[s][0] = True
    while hq:
        d, x = heappop(hq)
        if d % 3 == 0:
            dist[x] = min(dist[x], d // 3)
        d += 1
        for y in g[x]:
            if not can_reach[y][d%3]:
                can_reach[y][d%3] = True
                heappush(hq, (d, y))

    return dist[t] if dist[t] != inf else -1

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

N=int(input())
A=[int(_) for _ in input().split(" ")]

max=max(A)
if A[0] == max:
  total=0
  for i in range(len(A)):
    total = total + max - A[i]
  print(total)
  exit()

ans=0
total=0
b=len(A)
a=1

while a!=0:
  max=0
  for i in range(b):
    if max < A[i]:
      a=i
      max=A[i]
  for i in range(a+1,b):
    total += max - A[i]
  b=a

print(total)
    


### FIXED CODE ###

N=int(input())
A=[int(_) for _ in input().split(" ")]

max=0
total=0

for i in range(len(A)):
  if max < A[i]:
    max=A[i]
  else:
    total+=max-A[i]

print(total)
### BUGGY CODE ###

import sys

def main():
	input = sys.stdin.readline

	N, M = list(map(int,input().strip().split()))
	A = list(map(int,input().strip().split()))
	A.sort(reverse=True)

	for i in range(M):
		A[0] = A[0]/2

		larger = -1
		smaller = N-1
		target = A.pop(0)
		while larger-smaller!=-1:
			ind = int((larger+smaller)/2)
			if target>A[ind]:
				smaller = ind
			else:
				larger = ind

		A.insert(smaller,target)
		# print(A)

		# ind = 0
		# if N!=1:
		# 	while A[ind]<A[ind+1]:
		# 		A[ind], A[ind+1] = A[ind+1], A[ind]
		# 		ind = ind+1
		# 		if ind==N-1:
		# 			break

	print(sum(map(int,A)))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
	input = sys.stdin.readline

	N, M = list(map(int,input().strip().split()))
	A = list(map(int,input().strip().split()))
	A.sort(reverse=True)

	count = [0]*N
	ind = [0]
	for i in range(M):
		maximum = 0
		for j in ind:
			if A[j]>maximum:
				maxind = j
				maximum = A[j]

		if maximum==0: break

		# print(maxind)
		A[maxind] = A[maxind]/2
		count[maxind] += 1
		# print(count[maxind])
		if count[maxind]==len(ind):
			ind.append(0)
			# ind[-2] += 1
			ind[-2] = min(N-1,ind[-2]+1)
			# if ind[-1]!=N-1:
		else: 
			# ind[count[maxind]-1] += 1
			ind[count[maxind]-1] = min(N-1,ind[count[maxind]-1]+1)

		# print(ind)

	print(sum(map(int,A)))

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

from sys import stdin
S = (stdin.readline().rstrip())
Q = int(stdin.readline().rstrip())
cnt = 0
s = "@"
for i in range(Q):
    data = [(x) for x in stdin.readline().rstrip().split()]
    if data[0] == "2":
        if data[1] == "1":
            s = "".join([data[2],s])
            #S = data[2] + S
        else:
            #S = S + data[2]
            s = "".join([s,data[2]])
    else:
        s = s[::-1]
        cnt += 1
if cnt % 2 != 0:
    S = S[::-1]
ans = s.replace("@",S)
print(ans)

### FIXED CODE ###

from sys import stdin
from collections import deque
S = (stdin.readline().rstrip())
Q = int(stdin.readline().rstrip())
cnt = 0
ccnt = 0
s = deque(["@"])
for i in range(Q):
    data = [(x) for x in stdin.readline().rstrip().split()]
    if data[0] == "2":
        if data[1] == "1":
            if cnt % 2 == 0:
                s.appendleft(data[2])
            else:
                s.append(data[2])
        else:
            if cnt % 2 == 0:
                s.append(data[2])
            else:
                s.appendleft(data[2])
    else:
        cnt += 1
s = "".join(s)
if cnt % 2 != 0:
    s = s[::-1]
if cnt % 2 != 0:
    S = S[::-1]
ans = s.replace("@",S)
print(ans)
### BUGGY CODE ###

n = int(input())
l = []

for i in range(n):
    w = input()
    if w not in l:
        l.append(w)

print(len(l))

### FIXED CODE ###

n = int(input())
l = []
 
for i in range(n):
    l.append(input())
 
print(len(set(l)))
### BUGGY CODE ###

n,m=map(int,input().split())
count=0
s=[0]*(n+1)
 
for i in range(m):
  l,r=map(int,input().split())
  for j in range(l,r+1):
    s[j]+=1
    
for i in range(n+1):
  if s[i]==m:
    count+=1
    
print(count)

### FIXED CODE ###

n,m=map(int,input().split())
L=1
R=n
for i in range(m):
  l,r=map(int,input().split())
  L=max(l,L)
  R=min(r,R)

if (R-L+1)>=0:
  print(R-L+1)
else:
  print(0)
### BUGGY CODE ###

import sys
from sys import stdin

input = stdin.readline
sys.setrecursionlimit(10 ** 6)
 
def recursion_j(n, dp, i, j, k):
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    if i == j == k == 0:
        return 0
 
    res = 0
    if i > 0:
        res += recursion_j(n, dp, i - 1, j, k) * i
    if j > 0:
        res += recursion_j(n, dp, i + 1, j - 1, k) * j
    if k > 0:
        res += recursion_j(n, dp, i, j + 1, k - 1) * k
    res += n
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res
 
 
def p_j():
    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(n, dp, c[0], c[1], c[2]))
    
if __name__ == '__main__':
	p_j()

### FIXED CODE ###

def p_j_dp():
    n = int(input())
    *a, = map(int, input().split())
    c1 = a.count(1)
    c2 = a.count(2)
    c3 = a.count(3)
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    for k in range(c3 + 1):
        for j in range(c3 + c2 + 1 - k):
            for i in range(n + 1 - k - j):
                if i + j + k == 0:
                    continue
                res = n
                if i > 0:
                    res += i * dp[i - 1][j][k]
                if j > 0:
                    res += j * dp[i + 1][j - 1][k]
                if k > 0:
                    res += k * dp[i][j + 1][k - 1]
                res /= i + j + k
                dp[i][j][k] = res
    print(dp[c1][c2][c3])
    
p_j_dp()
### BUGGY CODE ###

N, K = map(int, input().split())
X, Y = [], []
D = []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    D.append((x, y))

X = sorted(X)
Y = sorted(Y)
num = float("inf")
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N - 1):
            for l in range(k + 1, N):
                tmp = 0
                for m in range(N):
                    if X[i] <= D[m][0] <= X[j] and Y[k] <= D[m][1] <= Y[l]:
                        tmp += 1
                if tmp >= K:
                    num = min(num, (X[j] - X[i]) * (Y[l] - Y[k]))

print(num)


### FIXED CODE ###

N, K = map(int, input().split())
X, Y = [], []
D = []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    D.append((x, y))

X = sorted(X)
Y = sorted(Y)
num = float("inf")
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N - 1):
            for l in range(k + 1, N):
                tmp = 0
                for m in range(N):
                    if X[i] <= D[m][0] <= X[j] and Y[k] <= D[m][1] <= Y[l]:
                        tmp += 1
                if tmp >= K:
                    num = min(num, (X[j] - X[i]) * (Y[l] - Y[k]))

print(num)
### BUGGY CODE ###

import math
import sys


if __name__ == '__main__':
    n = int(input())
    a_list = list(map(int, input().split()))

    max_a = max(a_list)
    a_list.remove(max_a)

    max_comb = - sys.maxsize
    answer1 = max_a
    answer2 = -1
    for i in range(n-1):
        comb = math.factorial(max_a)/(math.factorial(a_list[i]) * math.factorial(max_a - a_list[i]))
        if max_comb < comb:
            max_comb = comb
            answer2 = a_list[i]

    print(str(answer1) + " " + str(answer2))


### FIXED CODE ###

import math
import sys


if __name__ == '__main__':
    n = int(input())
    a_list = list(map(int, input().split()))

    max_a = max(a_list)
    a_list.remove(max_a)

    min_diff = sys.maxsize
    answer1 = max_a
    answer2 = -1
    for i in range(n-1):
        diff = math.fabs(max_a/2 - a_list[i])
        if min_diff > diff:
            min_diff = diff
            answer2 = a_list[i]

    print(str(answer1) + " " + str(answer2))
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())

    MAP = [[0]*N for x in range(N)]
    E = []
    for m in range(M):
        a,b,c = map(int, input().split())
        MAP[a-1][b-1] = c
        E.append((a-1,b-1,c))

    dp = [[-float('inf')]*N for x in range(2*N+1)]
    dp[0][0] = 0
    count = 1
    for i in range(2*N):  # N
        # for n in range(N):
        #     print(count,n)
        #     dp[count][n] = max(dp[count][n], dp[count-1][n])
        for e in E:
            a,b,c = e
            dp[count][b] = max(dp[count][b], dp[count-1][b], dp[count-1][a] + c)
        count += 1

    # print(dp[N-1][N-1], dp[N][N-1])
    if dp[2*N][N-1] == dp[N-1][N-1]:
        print(dp[N-1][N-1])
    else:
        print('inf')


if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()


### FIXED CODE ###

import math 
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    MAP = [[]*N for x in range(N)]
    E = []
    for m in range(M):
        a,b,c = map(int, input().split())
        MAP[a-1].append((b-1, c))
        E.append((a-1,b-1,c))

    dp = [-float('inf')]*N
    dp[0] = 0
    updated = set([0])
    for count in range(1, 2*N+1):  # N
        preupdated = list(updated)
        updated = set([])
        for a in preupdated:
            for b,c in MAP[a]:
                if max(dp[b], dp[b]) < dp[a] + c:
                    updated.add(b)
                    dp[b] = dp[a] + c
        if count == N-1:
            tmp = dp[N-1]

    # print(tmp, dp[N-1])
    if dp[N-1] == tmp:
        print(tmp)
    else:
        print('inf')


if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()
### BUGGY CODE ###

n,k=map(int,input().split())
p1=list(map(int,input().split()))
p2=[]
for i in range(n):
  p2.append(((1+p1[i])/2))
ans=sum(p2[0:k])
for j in range(n-k):
  if ans<sum(p2[j+1:j+k+1]):
    ans=sum(p2[j+1:j+k+1])
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p1=list(map(int,input().split()))
p2=[]
for i in range(n):
  p2.append(((1+p1[i])/2))
ans=sum(p2[0:k])
sum1=sum(p2[0:k])
for j in range(n-k):
  sum1=sum1+p2[j+k]-p2[j]
  if ans<sum1:
    ans=sum1
print(ans)