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

import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                if k<=80*80*40:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    res = 0
    while N:
        r = N%10
        N //= 10
        r_ = N%10
        if r < 5 or (r==5 and r_ < 5):
            res += r
        else:
            res += 10-r
            N += 1
    return str(res)

if __name__ == '__main__':
    print(solve())



### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N = input()[::-1]+'00'
    res = 0
    c = 0
    for i in range(len(N)-1):
        r = int(N[i])+c
        c = r//10
        r %= 10
        r_ = (int(N[i+1])+c)%10
        if r < 5 or (r==5 and r_ < 5):
            res += r
        else:
            res += 10-r
            c += 1
    return str(res)

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

N = int(input())

for n in range(1, N+1):
    ans = 0
    for x in range(1, int(n**(1/2))+1):
        for y in range(1, int(n**(1/2))+1):
            c = x**2 + y**2 + x*y - n
            b = x+y
            if b**2 - 4*c >= 0:
                d = (-b+(b**2-4*c)**(1/2))/2
                if int(d) == d and d >= 1:
                    ans += 1
    print(ans)


### FIXED CODE ###


N = int(input())
a = []
for n in range(1, N+1):
    ans = 0
    for x in range(1, int(n**(1/2))+1):
        for y in range(x, int(n**(1/2))+1):
            c = x**2 + y**2 + x*y - n
            b = x+y
            if b**2 - 4*c >= 0:
                d = (-b+(b**2-4*c)**(1/2))/2
                if int(d) == d and d >= 1:
                    if x != y:
                        ans += 2
                    else:
                        ans += 1
    print(ans)
### BUGGY CODE ###

from sys import stdin
from collections import deque
N, M = map(int, stdin.readline().rstrip().split())
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort()
A = deque(A)
Y = []
for _ in range(M):
    b, c = [int(x) for x in stdin.readline().rstrip().split()]
    Y.extend([c] * b)
Y.sort()
Y = deque(Y)

for i in range(len(Y) if len(Y) < len(A) else len(A)):
    a = A.popleft()
    c = Y.pop()
    if a < c:
        A.append(c)
    else:
        A.append(a)
        print(sum(A))
        quit()
print(sum(A))

### FIXED CODE ###

from sys import stdin
from collections import deque
from operator import itemgetter

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort()
A = deque(A)
X = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
X.sort(key=itemgetter(1), reverse=True)
D = []
for b, c in X:
    if len(D) < N:
        D.extend([c] * b)
    else:
        break
D = deque(D)

for i in range(len(D) if len(D) < len(A) else len(A)):
    a = A.popleft()
    c = D.popleft()
    if a < c:
        A.append(c)
    else:
        A.append(a)
        print(sum(A))
        quit()
print(sum(A))
### BUGGY CODE ###

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

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

def cf(x1,x2):
    cf=[]
    for i in range(1,gcd(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def is_prime(z):
  for i in range(2,int(z**0.5)+1):
    if i*i > z:
      break
    if z % i == 0:
      return False
  return True

tmp=cf(a,b)
sum=0
y=[]
for k in tmp:
  if is_prime(k):
    sum += 1

print(sum)

### FIXED CODE ###

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

def cf(x1,x2):
    cf=[]
    n =max(x1,x2)
    m=min(x1,x2)
    for i in range(1,int(m**0.5)+1):
        if m % i == 0:
          if n % i == 0:
            cf.append(i)
          if i != m//i and n % (m//i) == 0:
            cf.append(m//i)
    return cf

def is_prime(z):
  for i in range(2,int(z**0.5)+1):
    if i*i > z:
      break
    if z % i == 0:
      return False
  return True

tmp=cf(a,b)
sum=0
y=[]
for k in tmp:
  if is_prime(k):
    sum += 1

print(sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')
import numpy as np

def main():
	h,w,k=MI()
	G=[]
	for i in range(h):
		A=input().rstrip()
		A=list(map(int,A))
		G.append(A)
	G=np.array(G)
	#G=np.cumsum(G,axis=1)
	#print(G)

	an=10**10

	for i in range(1<<h-1):
		ans=h-1
		B=np.copy(G)
		for j in range(h):
			if i&(1<<j):
				ans-=1
				B[j+1]+=B[j]
				B[j]=[0]*w
		C=np.zeros(h)
		#print(B)

		for i in range(w):
			C+=B[:,i]
			#print(C)
			if np.max(C)>k:
				ans+=1
				C=B[:,i]
		an=min(an,ans)
		#print(ans)
	print(an)
















if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

def main():
	h,w,k=MI()
	G=[]
	for i in range(h):
		A=list(map(int,input().rstrip().decode()))
		G.append(A)
	#print(G)

	for i in range(h):
		for j in range(w):
			if i!=0:
				G[i][j]+=G[i-1][j]
			if j!=0:
				G[i][j]+=G[i][j-1]
			if i!=0 and j!=0:
				G[i][j]-=G[i-1][j-1]
	#print(G)

	B=[]
	for i in range(2**(h-1)):
		C=[0,h-1]
		for j in range(h):
			if i&(1<<j):
				C.append(j)
				C.append(j+1)
		C.sort()
		B.append(C)

	#print(B)

	ans=10**10

	def check(x1,y1,x2,y2):
		ret=G[x2][y2]
		if x1 != 0:
			ret -= G[x1-1][y2]
		if y1 != 0:
			ret -= G[x2][y1-1]
		if x1 != 0 and y1 != 0:
			ret += G[x1-1][y1-1]
		return ret

	for D in B:
		#print(d)
		cnt=len(D)//2-1
		l=0
		ww=0
		f=0
		while ww<w and f==0:
			for i,j in zip(D[0::2],D[1::2]):
				#print(i,j)
				if check(i,l,j,ww)>k:
					#print(i,l,j,ww,check(i,l,j,ww))
					if l==ww:
						f=1
					else:
						cnt+=1
						l=ww
					break
			ww+=1
			#print(w,ww,cnt)
		#print(D,cnt)
		if f==0:
			ans=min(ans,cnt)
	print(ans)














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

#設定
import sys
input = sys.stdin.buffer.readline

from heapq import heappop, heappush

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	F = getlist()
	A = sorted(A)
	F = sorted(F)
	Q = []
	for i in range(N):
		heappush(Q, [ (-A[i]) * F[N - 1 - i], -A[i], -F[N - 1 - i]])
	#print(Q)
	#処理
	for i in range(K):
		if Q[0][0] == 0:
			break
		else:
			s, a, f = heappop(Q)
			a += 1
			s = -(a * f)
			heappush(Q, [s, a, f])
	#print(Q)
	ans = 0
	for i in range(N):
		ans = max(ans, -Q[i][0])
	print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

#設定
import sys
input = sys.stdin.buffer.readline

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#二分探索基本形 L:リスト x:値 n:リスト長
def Binary_Search(A, F, N, K):
	#初期化
	left = 0
	right = 10 ** 12
	ans = INF
	
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		cnt = 0
		for i in range(N):
			if A[i] * F[i] > mid:
				cnt += (A[i] - int(mid // F[i]))
		if cnt <= K:
			right = mid - 1
			ans = min(ans, mid)
		else:
			left = mid + 1

	return ans

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	F = getlist()
	A = sorted(A)
	F = sorted(F)[::-1]
	ans = Binary_Search(A, F, N, K)
	print(ans)

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

n, k = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]

MOD = 998244353

dp = [0] * n
dp[0] = 1

for i in range(n):
  for l, r in LR:
    for j in range(l, r + 1):
      if i - j >= 0:
        dp[i] += dp[i - j]
        dp[i] %= MOD

print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]

MOD = 998244353

dp = [0] * n
dp[0] = 1

ruidp = [0] * (n + 1)
ruidp[1] = 1


for i in range(n):
  for l, r in LR:
    dp[i] += (ruidp[max(i - l + 1, 0)] - ruidp[max(i - r, 0)])
    dp[i] %= MOD
  ruidp[i + 1] = ruidp[i] + dp[i] 
  ruidp[i + 1] %= MOD

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

import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),k)
ans=1e25
for i in c:
    x=[]
    y=[]
    for j in i:
        x.append(l[j][0])
        y.append(l[j][1])
    ans=min(ans,(max(x)-min(x))*(max(y)-min(y)))
print(ans)


### FIXED CODE ###

import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),2)
d=itertools.combinations(range(n),2)
ans=10**25
for i0 in range(n):
    for i1 in range(i0,n):
        for j0 in range(n):
            for j1 in range(j0,n):
                i=[i0,i1]
                j=[j0,j1]
                #print(i,j)
                lx=min(l[i[0]][0],l[i[1]][0])
                rx=max(l[i[0]][0],l[i[1]][0])
                dy=min(l[j[0]][1],l[j[1]][1])
                uy=max(l[j[0]][1],l[j[1]][1])
                tk=0
                for p in l:
                    if lx<=p[0]<=rx and dy<=p[1]<=uy:
                        tk+=1
                if tk>=k:
                    ans=min(ans,(uy-dy)*(rx-lx))
print(ans)
### BUGGY CODE ###

S=input()
Q=int(input())

# deq=deque()
# for s in S:
#     deq.append(s)

rev=False
ans=""
ans+=S
for _ in range(Q):
    query=input().split()
    if query[0]=="1":
        rev = not rev
        # print(rev)
    else:
        if rev:
            query[1]=str(3-int(query[1]))
        if query[1]=="1":
            # deq.appendleft(query[2])
            ans=query[2]+ans
        else:
            # deq.append(query[2])
            ans=ans+query[2]

# if rev:
#     deq.reverse()
# # ans=""
# for i in range(len(deq)):
#     ans+=deq[i]

if not rev:
    print(ans)
else:
    print(ans[::-1])

### FIXED CODE ###

S=input()
Q=int(input())

# deq=deque()
# for s in S:
#     deq.append(s)

rev=False
front=""
last=""
# ans+=S

for _ in range(Q):
    query=input().split()
    if query[0]=="1":
        rev = not rev
        # print(rev)
    else:
        if rev:
            query[1]=str(3-int(query[1]))
        if query[1]=="1":
            # deq.appendleft(query[2])
            front=query[2]+front
        else:
            # deq.append(query[2])
            last+=query[2]

# if rev:
#     deq.reverse()
# # ans=""
# for i in range(len(deq)):
#     ans+=deq[i]

if not rev:
    print(front+S+last)
else:
    print(last[::-1]+S[::-1]+front[::-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans *= i
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
ans = 1
A = [int(i) for i in input().split()]
ans = 1
for i in A:
    ans *= i
    if ans > 10**18:
        ans = -1
        break
if 0 in A:
    ans = 0
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if dist[q]<=dist[p]:
                    continue
                if abs(dy)+abs(dx)==1:
                    dq.appendleft(q)
                    dist[q] = dist[p]
                else:
                    dq.append(q)
                    dist[q] = dist[p] + 1

print(-1 if dist[goal]==10**10 else dist[goal])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])
### BUGGY CODE ###

from collections import deque

def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, input().split())
    total_cells = H * W
    existing_black_cells = 0

    grid = []
    for i in range(H):
        line = input()
        existing_black_cells += line.count('#')
        grid.append(line)

    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    movement = 0

    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            visited.add(coodinate)
            y = coodinate[0]
            x = coodinate[1]

            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return

            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
    print(-1)
    return
main()

### FIXED CODE ###

import sys
from collections import deque
    
def main(*args, **kwargs):
    # Initialize data
    H, W = map(int, sys.stdin.readline().split())
    total_cells = H * W
    existing_black_cells = 0
 
    grid = []
    for i in range(H):
        line = sys.stdin.readline()
        existing_black_cells += line.count('#')
        grid.append(line)
 
    # Initialize Search
    queue = deque()
    queue.append((0, 0))  # start point
    visited = set()
    visited.add((0, 0))
    movement = 0
 
    while len(queue) > 0:
        movement += 1
        for i in range(len(queue)):  # Process same level
            coodinate = queue.popleft()
            y = coodinate[0]
            x = coodinate[1]
 
            # Terminate condition
            if y == H - 1 and x == W - 1:
                print(total_cells - movement - existing_black_cells)
                return
 
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                X = x + dx
                Y = y + dy
                adjacent = (Y, X)
                if 0 <= X < W and 0 <= Y < H and grid[Y][X] == '.' and adjacent not in visited:
                    queue.append(adjacent)
                    visited.add(adjacent)
    print(-1)
    return
main()
### BUGGY CODE ###

S = str(input())
ans = 0
for i in range(len(S)+1):
    for j in range(i+1,len(S)+1):
        if(int(S[i:j]) % 2019 == 0):
            ans += 1
print(ans)

### FIXED CODE ###

S = str(input())
# 余りのリスト
counts = [0] * 2019
n, d = 0, 1

for s in S[::-1]:
    n += int(s) * d
    d *= 10
    n %= 2019
    d %= 2019
    counts[n] += 1
ans = counts[0]
for count in counts:
    ans += count * (count - 1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
memo=[]

h=0; w=0
for element in a:
    if element in memo: pass
    else:
        memo.append(element)
        num=a.count(element)
        if num>=4 and h==0: h=w=element
        elif num>=2 and h==0: h=element
        elif num>=2 and w==0: w=element

ans=h*w
print(ans)

### FIXED CODE ###

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

ans=[]
tmp=0
count=0
for el in a:
    if len(ans)==2: break
    if el != tmp: tmp=el; count=0
    else:
        if count%2==0: ans.append(el); tmp=el;
        count+=1

try: ans=ans[0]*ans[1]
except: ans=0
print(ans)
### BUGGY CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N, K = map(int, input().split())
A = list(map(int, input().split()))
L = []
for i in set(A):
    L.append(A.count(i))
L.sort()
if len(set(A)) <= K:
    print('0')
else:
    print(str(sum(L[0:len(set(A))-K])))


### FIXED CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = set(A)
    L = [0 for i in range(N+1)]
    for i in A:
        L[i] += 1
    L.sort()
    if len(B) <= K:
        print('0')
    else:
        print(str(sum(L[0:N+1-K])))


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

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))




    n = 10 ** 6
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    prime_list = [i for i in range(n + 1) if is_prime[i]]




    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
            else:
                tmpnum *= k ** v
        ans += tmpnum
    ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

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

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        ans += a
    ans %= mod

    print(ans)




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

from heapq import heappush, heappop
from collections import deque


def bfs(x, y):
    path = [float('inf')] * N
    q = deque()
    q.append(x)
    path[x] = 0
    while q:
        p = q.popleft()
        for np, d in edge[p]:
            if path[np] > path[p] + d:
                path[np] = path[p] + d
                q.append(np)
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        heappush(q, (A[i][j], i, j))

ans = 0
edge = [[] for _ in range(N)]
while q:
    a, i, j = heappop(q)
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)


### FIXED CODE ###

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

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print(-1)
            exit()

print(cnt // 2)
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
k=min(k,41)

for j in range(k):
    b=np.zeros_like(a)
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    for i in range(1,n):
        b[i]+=b[i-1]
    a=b
print(" ".join(map(str,a)))

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
k=min(k,41)

for j in range(k):
    b=[0 for i in range(n)]
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    for i in range(1,n):
      b[i]+=b[i-1]
    a=b
print(" ".join(map(str,a)))