Harryxun/stf_run huggingface dataset:
import numpy as np

def knapsack2(N,W,weight,value,WW):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(WW)] for j in range(N+1)]
  for i in range(WW):
      dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(WW):
      if weight[i]<=w:
        if w-weight[i]>=W: #時間切れ
          dp[i+1][w]=dp[i][w]
        else: #注文可能
          dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #NG
        dp[i+1][w]=dp[i][w]
  return np.max(np.array(dp))
  #return dp[N][2*W]

N, T = map(int,input().split())
WW = T+3000
ab = []
for i in range(N):
    ab.append(tuple(map(int,input().split())))

weight = [elem[0] for elem in ab]
value = [elem[1] for elem in ab]
res = knapsack2(N,T,weight,value,WW)
print(res)


### FIXED CODE ###

#import numpy as np

def knapsack2(N,W,weight,value,WW):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(WW)] for j in range(N+1)]
  for i in range(WW):
      dp[0][i]=0
  maxval = 0
  #DP
  for i in range(N):
    for w in range(WW):
      if weight[i]<=w:
        if w-weight[i]>=W: #時間切れ
          dp[i+1][w]=dp[i][w]
        else: #注文可能
          dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #NG
        dp[i+1][w]=dp[i][w]
    maxval = max([maxval, max(dp[i+1])])
#  for elem in dp:
#    print(elem[:2*W])
  return maxval
  #return np.max(np.array(dp))
  #return dp[N][2*W]

N, T = map(int,input().split())
WW = T+3000
ab = []
for i in range(N):
    ab.append(tuple(map(int,input().split())))

ab =  sorted(ab,key=lambda x:x[0])

weight = [elem[0] for elem in ab]
value = [elem[1] for elem in ab]
res = knapsack2(N,T,weight,value,WW)
print(res)
n,a,b = map(int, input().split())

cursum = 0

for n in range(1, l[0]+1):
    x = sum(map(int, str(n)))
    if a <= x and x <= b:
        cursum += n

print(cursum)

### FIXED CODE ###

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

cursum = 0

for x in range(1, n+1):
    y = sum(map(int, str(x)))
    if a <= y and y <= b:
        cursum += x

print(cursum)
def main():
    import sys
    input = sys.stdin.readline

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

    # num = N//B

    # score = 0
    # for x in range(1, N+1):
    #     tmp = int(A*x/B) - A*int(x/B)
    #     if score <= tmp:
    #         score = tmp
    # print(score)

    import numpy as np

    arr = np.arange(N)
    arr = np.modf(arr/B)[0]
    print(int(max(arr*A)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

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

    x = min(B-1, N)
    print(int(A*x/B)-A*int(x/B))


if __name__ == "__main__":
    main()
def gcd(x,y):
   tmp = x
    x = x if x >= y else y
    if tmp != x:
        y = tmp
    if y == 0:
        return x
    return gcd(x%y, y)
    
A,B =  [int(x) for x in input().split(" ")]
def lcm(x, y):
    return (x * y) // gcd(x, y)
print(lcm(A,B))




### FIXED CODE ###

def gcd(x,y):
    tmp = x
    x = x if x >= y else y
    if tmp != x:
        y = tmp
    if y == 0:
        return x
    return gcd(x%y, y)

A,B =  [int(x) for x in input().split(" ")]
def lcm(x, y):
    return (x * y) // gcd(x, y)
print(lcm(A,B))
a,b = [int(i) for i in input().split()]

l = [int(i) for i in input().split()]

l2 = [i for i in l if i %2 == 1]

if not l2 :
    print(2**n if b == 0 else 0)
else:
    print(2**(a-1))

### FIXED CODE ###

a,b = [int(i) for i in input().split()]

l = [int(i) for i in input().split()]

l2 = [i for i in l if i %2 == 1]

if not l2 :
    print(2**a if b % 2 == 0 else 0)
else:
    print(2**(a-1))
a=int(input())
b=int(input())

print(a*b)
print(2*a+2*b)


### FIXED CODE ###

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

print(a*b,2*a+2*b)
import numpy as np

H,W=input().split()
h,w=input().split()

mat=np.ones((H,W))
mat[0:h,:]=0
mat[:,0:w]=0

print(np.sum(mat))

### FIXED CODE ###

# -*- Coding: utf-8 -*-

import numpy as np

INPUT=input().split()
Input=input().split()
H,W=int(INPUT[0]),int(INPUT[1])
h,w=int(Input[0]),int(Input[1])

mat=np.ones((H,W))
mat[0:h,:]=0
mat[:,0:w]=0

print(int(np.sum(mat)))
N = int(input())
rint(int(((N-1) * N)/2))

### FIXED CODE ###

N = int(input())
print(((N-1) * N)//2)
a,b=map(int,input().split())
if a%2!=0 and b%!=0:
  print("Odd")
else:print("Even")

### FIXED CODE ###

a,b=map(int,input().split())
if a%2!=0 and b%2!=0:
  print("Odd")
else:print("Even")
n = int(input())

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

count = 1

for i in a:
    count*=i

x = 10**18

if count > x:
    print(-1)
    break
else:
    print(count)

### FIXED CODE ###

n = int(input())

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

count = 1

for i in range(n):
    count*=a[i]
    if count>10**18:
        print(-1)
        break

else:
    print(count)
N, M = map(int, input().split())

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

visited = [0]*N
visited[0] = 1

def dfs(v, visited):
    if 0 not in visited:
        return 1

    ans = 0
    for i in G[x]:
        if visited[i] == 0:
            visited[i] = 1
            ans += dfs(i, visited)
            visited[i] = 0

    return ans

print(dfs(0, visited))

### FIXED CODE ###


import itertools

N, M = map(int, input().split())
adj_matrix = [[0]* N for _ in range(N)]

for i in range(M): #隣接行列
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)
#!/usr/bin/env python
# coding: utf-8

def no():
    print("No")
    return

def main():
    s = input()
    x, y = list(map(int, input().split()))
    x_start = 0
    f_count = 0
    x_dirs = []
    y_dirs = []
    is_x = True # xを向いてるか
    t_exist = False
    for c in s:
        if c == "F":
            f_count += 1
            continue
        # T
        if f_count > 0:
            if is_x:
                if t_exist:
                    x_dirs.append(f_count)
                else:
                    x_start = f_count
            else:
                y_dirs.append(f_count)
        t_exist = True
        is_x = not is_x
        f_count = 0
        continue
    if f_count > 0:
        if is_x:
            if t_exist:
                x_dirs.append(f_count)
            else:
                x_start = f_count
        else:
            y_dirs.append(f_count)

    memo_x = [{} for _ in range(len(x_dirs)+1)]
    memo_y = [{} for _ in range(len(y_dirs)+1)]
    memo_x[0][x_start] = True
    memo_y[0][0] = True

    for i, dx in enumerate(x_dirs):
        for j in memo_x[i]:
            memo_x[i+1][j-dx] = True
            memo_x[i+1][j+dx] = True
    for i, dy in enumerate(y_dirs):
        for j in memo_y[i]:
            memo_y[i+1][j-dy] = True
            memo_y[i+1][j+dy] = True

    # print(x_dirs, y_dirs)
    # print(memo_x)
    # print(memo_y)

    if x not in memo_x[len(x_dirs)]:
        return no()
    if y not in memo_y[len(y_dirs)]:
        return no()
    print("Yes")


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8


def main():
    a, b = list(map(int, input().split()))
    x = (a+b+1)//2
    print(x)


if __name__ == '__main__':
    main()
import sys
input = sys.stdin.buffer.readline

def gcd(a: int, b: int):
    """ https://cocodrips.hateblo.jp/entry/2014/03/05/143623
    """
    while b:
        a, b = b, a%b
    return a

def lcm(a: int, b: int):
    return a * b // gcd(a, b)


def main():
    N = int(input())
	#N, M = map(int, input().split())
    #print(lcm(N, M))
	print("ABC" if N<1000 else "ABD")

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def gcd(a: int, b: int):
    """ https://cocodrips.hateblo.jp/entry/2014/03/05/143623
    """
    while b:
        a, b = b, a%b
    return a

def lcm(a: int, b: int):
    return a * b // gcd(a, b)


def main():
    N = int(input())
    #N, M = map(int, input().split())
    #print(lcm(N, M))
    print("ABC" if N<1000 else "ABD")


if __name__ == "__main__":
    main()
from math import *

def lcm(a, b):
    return a * b // gcd(a, b)

n = int(input())
a = input().split()

for i in range(n):
    a[i] = int(a[i])

l = 1
for i in range(n):
    l = lcm(l, a[i])

l -= 1
s = 0

for i in range(n):
    s += l % a[i]

print(s)

### FIXED CODE ###

n = int(input())
a = input().split()
s = 0
for i in range(n):
    s += int(a[i])
print(s - n)
n,t = map(int, input().split())
a = []
cost = float(10000)
for i in range(n):
    a,b = list(map(int, input().split()))
    if b <= t:
        cost = min(cost, a)

print('TLE' if cost == 10000 else co

### FIXED CODE ###

n,t = map(int, input().split())
a = []
for i in range(n):
    aa = list(map(int, input().split()))
    a.append(aa)

cost = float(10000)
for a in a:
    if a[1] <= t and a[0] < cost:
        cost = a[0]

if cost == 10000:
    cost = 'TLE'
print(cost)
import numpy as np
ab = input().split(" ")
print(np.round(np.mean(int(ab[0]), int(ab[1]))))

### FIXED CODE ###

import numpy as np
ab = input().split(" ")
print(int(np.ceil(np.mean([int(ab[0]), int(ab[1])]))))
# !/usr/bin python3
# -*- coding: utf-8 -*-

rgb = int(input().strip(' '))

if rgb % 4 == 0:
    print('YES')

else:
    print('NO')

### FIXED CODE ###

# !/usr/bin python3
# -*- coding: utf-8 -*-

rgb = int(input().replace(" ", ""))

if rgb % 4 == 0:
    print('YES')

else:
    print('NO')
n = int(input())
li = list(n)
sn = sum(li)
if ( n % sn ): print("Yes")
else: print("No")

### FIXED CODE ###

n = int(input())
li = list(str(n))
li_ = [int(i) for i in li]
allSum = sum(li_)
if not n % allSum: print("Yes")
else: print("No")
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*N
dp[0] = 0
 
 
for i in range(1,N):
    dp[i] = min(dp[i-j]+abs(h[i] - h[i-j]) for j in range(1,min(K,i)))
print(dp[N-1])

### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

def check(max_length, left, right, r, index):
    if index == 1000:
        print(left)
    half = (left + right) / 2
    if 2 * half <= max_length * (r - half) / r:
        check(max_length, half, right, r, index + 1)
    else:
        check(max_length, left, half, r, index + 1)

def main():
    data = [list(map(int, input().split())) for i in range(3)]
    a = ((data[0][0] - data[1][0]) ** 2 + (data[0][1] - data[1][1]) ** 2) ** 0.5
    b = ((data[1][0] - data[2][0]) ** 2 + (data[1][1] - data[2][1]) ** 2) ** 0.5
    c = ((data[0][0] - data[2][0]) ** 2 + (data[0][1] - data[2][1]) ** 2) ** 0.5

    s = (a + b + c) / 2
    S = (s * (s - a) * (s - b) * (s - c)) ** 0.5
    r = 2 * S / (a + b + c)

    left, right = 0, max(a, b, c)

    check(max(a, b, c), left, right, r, 0)





if __name__ == '__main__':
    main()
    # test()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

def check(max_length, left, right, r, index):
    if index == 1000:
        print(left)
        sys.exit()
    half = (left + right) / 2
    if 2 * half <= max_length * (r - half) / r:
        check(max_length, half, right, r, index + 1)
    else:
        check(max_length, left, half, r, index + 1)

def main():
    data = [list(map(int, input().split())) for i in range(3)]
    a = ((data[0][0] - data[1][0]) ** 2 + (data[0][1] - data[1][1]) ** 2) ** 0.5
    b = ((data[1][0] - data[2][0]) ** 2 + (data[1][1] - data[2][1]) ** 2) ** 0.5
    c = ((data[0][0] - data[2][0]) ** 2 + (data[0][1] - data[2][1]) ** 2) ** 0.5

    s = (a + b + c) / 2
    S = (s * (s - a) * (s - b) * (s - c)) ** 0.5
    r = 2 * S / (a + b + c)

    left, right = 0, max(a, b, c)

    check(max(a, b, c), left, right, r, 0)





if __name__ == '__main__':
    main()
    # test()
s = input()
if s.issupper == True:
  print("A")
else:
  print("a")

### FIXED CODE ###

s = str(input())
if s.isupper():
  print("A")
else:
  print("a")
list = []
while True:
    if(int(input()) == 0): break
    else: list.append(input())
    
for i in len(list):
    print("Case %d:%d" %(i,list[i]))


### FIXED CODE ###

list = []
while True:
    a = int(input())
    if(a == 0): break
    else: list.append(a)
    

for i in range(len(list)):
    print("Case %d: %d" %(i+1,list[i]))
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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


s = input()
l = len(s)

ans = 0

m = int('1'*(l-1), 2)
for i in range(m+1):
	now = format(i, 'b').zfill(l-1)
	tmp = s[0]
	for k in range(l-1):
		if now[k] == '0':
			tmp += s[k+1]
		else:
			ans += int(tmp)
			tmp = s[k+1]
	ans += int(tmp)
print(ans)


### FIXED CODE ###

# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

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


s = input()
l = len(s)

if l == 1:
	print(int(s))
else:
	ans = 0

	m = int('1'*(l-1), 2)
	for i in range(m+1):
		now = format(i, 'b').zfill(l-1)
		tmp = s[0]
		for k in range(l-1):
			if now[k] == '0':
				tmp += s[k+1]
			else:
				ans += int(tmp)
				tmp = s[k+1]
		ans += int(tmp)
	print(ans)
def factorize(x):
    p = 2
    f = {}
    while x*x>=p:
        if x%p==0: f[p]=0
        while x%p==0:
            f[p]+=1
            x//=p
        p+=1
    if x>1: f[x]=1
    return f

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

F = {}

for a in A:
    for f in set(factorize(a)):
        if f not in F: F[f] = 0
        F[f] += 1

m = max(F.values())
if m<=1:
    print('pairwise coprime')
elif m<N:
    print('setwise coprime')
else:
    print('not coprime')
    


### FIXED CODE ###

def factorize(x):
    f = set()
    if x%2==0: f.add(2)
    while x%2==0: x//=2
    
    p = 3
    while x>=p*p:
        if x%p==0: f.add(p)
        while x%p==0: x//=p
        p+=2
    if x>1: f.add(x)
    return f

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

F = [0]*(10**6+5)

for a in A:
    for f in factorize(a):
        F[f] += 1

m = max(F)
if m<=1:
    print('pairwise coprime')
elif m<N:
    print('setwise coprime')
else:
    print('not coprime')
import sys

s = list(input())
t = list(input())

for i in range(len(t)):
    if t[i] not in s:
        print(-1)
        sys.exit()

i = 0
n = 0
for i in range(len(s)):
    if len(s) == i + n:
        break
    
    if s[i] not in t:
        s.pop(i)
        n += 1

count = 0
for j in range(100000):
    for k in range(len(s)):
        if count == len(t):
            print(k +  (j * len(s)) + n * (j + 1))
            sys.exit()
            
        #print(a[k +  (j * len(s))], t[count],a, count)
        if s[k] == t[count]:
            count += 1

print(-1)

### FIXED CODE ###

s = input()
t = input()
t_length = len(t)

temp = s[:]
count = 0
ans = 0

for i in range(len(t)):
    a = s.find(t[i])
    if a == -1:
        print(-1)
        exit()

while count < t_length:
    value = temp.find(t[count])
    if value == -1:
        ans += len(temp)
        temp = s[:]
    
    else:
        ans += value + 1
        count += 1
        temp = temp[value + 1:]

print(ans)
A, B, C, D = map(int, input().split())
if A + B + C + D == 7:
  print('{}+{}+{}+{}=7'.format(A, B, C, D))
elif A + B + C - D == 7:
  print('{}+{}+{}-{}=7'.format(A, B, C, D))
elif A + B - C + D == 7:
  print('{}+{}-{}+{}=7'.format(A, B, C, D))
elif A + B - C - D == 7:
  print('{}+{}-{}-{}=7'.format(A, B, C, D))
elif A - B + C + D == 7:
  print('{}-{}+{}+{}=7'.format(A, B, C, D))
elif A - B + C - D == 7:
  print('{}-{}+{}-{}=7'.format(A, B, C, D))
elif A - B - C + D == 7:
  print('{}-{}-{}+{}=7'.format(A, B, C, D))
else:
  print('{}-{}-{}-{}=7'.format(A, B, C, D))


### FIXED CODE ###

abcd = input()
A,B,C,D = int(abcd[0]),int(abcd[1]),int(abcd[2]),int(abcd[3])    
if A + B + C + D == 7:
  print('{}+{}+{}+{}=7'.format(A, B, C, D))
elif A + B + C - D == 7:
  print('{}+{}+{}-{}=7'.format(A, B, C, D))
elif A + B - C + D == 7:
  print('{}+{}-{}+{}=7'.format(A, B, C, D))
elif A + B - C - D == 7:
  print('{}+{}-{}-{}=7'.format(A, B, C, D))
elif A - B + C + D == 7:
  print('{}-{}+{}+{}=7'.format(A, B, C, D))
elif A - B + C - D == 7:
  print('{}-{}+{}-{}=7'.format(A, B, C, D))
elif A - B - C + D == 7:
  print('{}-{}-{}+{}=7'.format(A, B, C, D))
else:
  print('{}-{}-{}-{}=7'.format(A, B, C, D))
l=[i for i in str(input())]
A=int(''.join(l[:2]))
B=int(''.join(l[2:]))

if A==00 or A>=13:
  if B==00 or B>=13:
    print('NA')
  else:
    print('YYMM')
elif A>=01 and A<=12:
  if B==00 or B>=13:
    print('MMYY')
  else:
    print('AMBIGUOUS')
  

### FIXED CODE ###

l=[i for i in str(input())]
A=int(''.join(l[:2]))
B=int(''.join(l[2:]))

if A==0 or A>=13:
  if B==0 or B>=13:
    print('NA')
  else:
    print('YYMM')
elif A>=1 and A<=12:
  if B==0 or B>=13:
    print('MMYY')
  else:
    print('AMBIGUOUS')
s = input()
N = len(s)
D = {}
for i in range(N):
    if s[i] in D:
        D[s[i]] += 1
    else:
        D[s[i]] = 1
my_g = (N+1)//2
my_p = N//2
score = my_p - D["p"]
print(score)

### FIXED CODE ###

s = input()
N = len(s)
D = {"g":0, "p":0}
for i in range(N):
    D[s[i]] += 1
my_p = N//2
score = my_p - D["p"]
print(score)
in = input()
d = {'SUN': 7, 'MON': 6, 'TUE': 5, 'WED': 4, 'THU': 3, 'FRI': 2, 'SAT': 1}
print(d[in])

### FIXED CODE ###

a = input()
d = {'SUN': 7, 'MON': 6, 'TUE': 5, 'WED': 4, 'THU': 3, 'FRI': 2, 'SAT': 1}
print(d[a])
def main():
    data = list(map(int, input().split()))
    Xn = data[0]
    Yn = data[1]
    X = data[2]
    Y = data[3]

    Xs = list(map(int, input().split()))
    Ys = list(map(int, input().split()))

    mergin = list(range(X, Y))
    flag = false
    if not mergin:
        mergin.append(0)
        flag = true
    x_line = min(mergin)
    y_line = max(mergin)

    max_x = max(Xs)
    min_y = min(Ys)

    if (max_x < min_y):
        if ((max_x + min_y) // 2 in mergin):
            if flag:
                print('War')
            else:
                print('No War')
        else:
            if flag:
                print('No War')
            else:
                print('War')
    else:
        if flag:
            print('No War')
        else:
            print('War')

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    data = list(map(int, input().split()))
    Xn = data[0]
    Yn = data[1]
    X = data[2]
    Y = data[3]

    Xs = list(map(int, input().split()))
    Ys = list(map(int, input().split()))

    mergin = list(range(X, Y))
    x_line = min(mergin)
    y_line = max(mergin)

    max_x = max(Xs)
    min_y = min(Ys)

    if (max_x < min_y):
        if ((max_x + min_y) // 2 in mergin):
            print('No War')
        else:
            print('War')
    else:
        print('War')

if __name__ == "__main__":
    main()
n, m = map(int, input().split())
query = []
for i in range(m):
    qList = list(map(int, input().split()))
    query.append(qList)

for city in query:
    result[city[0]-1].append(city[1])

for i in range(n):
    result[i].sort()

for city in query:
    rank = result[city[0]-1].index(city[1])+1
    prefStr = "0"*(6-len(str(city[0]))) + str(city[0])
    rankStr = "0"*(6-len(str(rank))) + str(rank)
    resultStr = "{}{}".format(prefStr, rankStr)
    print(resultStr)

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
A = list(map(int,input.split(" ")))
if max(A) > 9:
	print("-1")
else:
	print(str(A[0] * A[1]))

### FIXED CODE ###

A = list(map(int,input().split(" ")))
if max(A) > 9:
	print("-1")
else:
	print(str(A[0] * A[1]))
a, b, k = map(int, input().split())
import math
g = math.gcd(a, b)
cnt = 0
for i in range(1, g+1):
    if g % i == 0:
        cnt += 1
    if cnt == k:
        print(i)
        break

### FIXED CODE ###

a, b, k = map(int, input().split())
cnt = 0
for i in reversed(range(1, 101)):
    if a%i==0 and b%i==0:
        cnt += 1
        if cnt == k:
            print(i)
            break
N=input()
products=[int(input()) for i in range(N)]
print(sum(products)-max(products)//2)

### FIXED CODE ###

N=int(input())
products=[int(input()) for i in range(N)]
print(sum(products)-max(products)//2)
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
ans_max = 0
V_ans=[]
C_ans=[]

for i in range(0,N):
    if V[i]>C[i]:
        V_ans.append(V[i])
        C_ans.append(C[i])
        
print(V_ans.sum-C_ans.sum)

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
ans_max = 0
V_ans=[]
C_ans=[]

for i in range(0,N):
    if V[i]>C[i]:
        V_ans.append(V[i])
        C_ans.append(C[i])

print(sum(V_ans)-sum(C_ans))
x = int(input())
y = int(input())
z = int(input())

a = z
b = x
c = y

print(str(a)+" "+str(b)+" "+str(c))

### FIXED CODE ###

x,y,z = input().split()

a = z
b = x
c = y

print(str(a)+" "+str(b)+" "+str(c))
def MAP():
    return map(int, input().split())

a,b=MAP()

t=1
cnt=0
while True:
    if b <= t:
        break
    t -= 1
    t += a
    cnt += 1
print(cnt)

### FIXED CODE ###

s=input()
t=input()

cnt=0
for i in range(3):
    if s[i] == t[i]:
        cnt+=1
print(cnt)
# ABC124C

s = input()
s = [int(t) for t in list(s)]
repaint = 0
for i in range(1, len(s)):
    if s[i-1] == s[i]:
        repaint += 1
        s[i] = 1 - s[i]
paint(repaint)


### FIXED CODE ###

# ABC124C

s = input()
s = [int(t) for t in list(s)]
repaint = 0
for i in range(1, len(s)):
    if s[i-1] == s[i]:
        repaint += 1
        s[i] = 1 - s[i]
print(repaint)
N = int(input())

S = []
for _ in range(N):
    tmp=sorted(input())
    S.append(tmp)

S.sort()

for i in range(len(S)):
    S[i]=''.join(S[i])

import collections
from math import factorial

c = collections.Counter(S)

res=0
for v in c.values():
    if v>1:
        res += factorial(v) / factorial(2) / factorial(v - 2)

print(int(res))

### FIXED CODE ###

N = int(input())

S = []
for _ in range(N):
    tmp=sorted(input())
    S.append(tmp)

for i in range(len(S)):
    S[i]=''.join(S[i])

import collections
from math import factorial

res=0
dic = {}
for tmp in S:
    if tmp in dic.keys():
        res+=dic[tmp]
        dic[tmp]+=1
    else:
        dic[tmp]=1

print(int(res))
n=int(input())
s=[1]
c=0
while s[-1]*3<n:s+=[s[-1]*3+1]
s=s[::-1]
a=[int(input())for _ in[0]*n]
for g in s:
 for i in range(n):
  k=a[i]
  j=i-g
  while j>=0 and a[j]>k:a[j+g]=a[j];j-=g;c+=1
  a[j+g]=k
print(len(s))
print(*s)
print(c)
for x in a:print(x)


### FIXED CODE ###

import sys
def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v
def solve():
    n = int(input())
    A = list(map(int, sys.stdin))
    G = [int((2.25**i - 1) / 1.25)for i in range(17, 0, -1)]
    G = [v for v in G if v <= n]
    for g in G:
        insertionSort(A, n, g)
    print(len(G))
    print(*G)
    print(cnt)
    print('\n'.join(map(str, A)))
if __name__ == '__main__':
    cnt = 0
    solve()