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

from itertools import product
with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

possible = True
ans = 0
r = range(N)
for i,j in product(r, r) :
    for k in r:
        if k == i or k == j:
            continue
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans//2 if possible else -1)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
### BUGGY CODE ###

n = int(input())
x = [int(x) for x in list(input())]
lx = len(x)-1

memo = [0]*(n+1)

for val in range(1, n+1):
    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1)//2
        else:
            tmp = tmp//2
    memo[val] = memo[val % cnt] + 1


xx = 0
xx_cnt = 0
for i, y in enumerate(x):
    xx += (1 << (lx-i))*y
    if y == 1:
        xx_cnt += 1

for i in range(n):
    if x[i] == 0:
        val = xx + (1 << (lx-i))*1
        cnt = xx_cnt + 1
    else:
        val = xx - (1 << (lx-i))*1
        cnt = xx_cnt - 1

    ans = 0
    if val == 0:
        print(ans)
    else:
        while val > n:
            ans += 1
            val = val % cnt
            tmp = val % cnt
            cnt = 0
            while tmp > 0:
                if tmp & 1:
                    cnt += 1
                    tmp = (tmp-1) // 2
                else:
                    tmp = tmp // 2
        print(memo[val]+ans)


### FIXED CODE ###

n = int(input())
x = [int(x) for x in list(input())]

x_cnt = 0
for i, y in enumerate(x):
    if y == 1:
        x_cnt += 1

aa = x_cnt + 1
bb = x_cnt - 1

a = [1 % aa]
if bb > 0:
    b = [1 % bb]
else:
    bb = 1
    b = [0]

for _ in range(n-1):
    a.append(a[-1]*2 % aa)
    b.append(b[-1]*2 % bb)

a = a[::-1]
b = b[::-1]

x_ps = 0
x_ng = 0
for i, val in enumerate(x):
    if val == 1:
        x_ps += a[i]
        x_ng += b[i]

for i in range(n):
    ans = 0
    if x[i] == 0:
        cnt = x_cnt + 1
        val = (x_ps + a[i]) % cnt
    else:
        cnt = x_cnt - 1
        if cnt == 0:
            print(ans)
            continue
        val = (x_ng - b[i]) % cnt
    ans += 1

    tmp = val
    cnt = 0
    while tmp > 0:
        if tmp & 1:
            cnt += 1
            tmp = (tmp-1) // 2
        else:
            tmp = tmp // 2

    if cnt == 0:
        print(ans)
        continue

    while val > 0:
        ans += 1
        val = val % cnt
        tmp = val % cnt
        cnt = 0
        while tmp > 0:
            if tmp & 1:
                cnt += 1
                tmp = (tmp-1) // 2
            else:
                tmp = tmp // 2
    print(ans)
### BUGGY CODE ###

from itertools import product

N = int(input())
XYP = [tuple(map(int, input().split())) for _ in range(N)]
X = [x for x, _, _ in XYP]
Y = [y for _, y, _ in XYP]
INF = 10**18

def calcCost(AP, A):
    ret = [[INF] * N for _ in range(1 << N)]
    for state in range(1 << N):
        useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
        for i, (a, p) in enumerate(AP):
            cost = abs(a)
            for z in useA:
                cost = min(cost, abs(a - z))
            ret[state][i] = cost * p
    return ret

costX = calcCost([(x, p) for x, _, p in XYP], X)
costY = calcCost([(y, p) for _, y, p in XYP], Y)

def makeState(state, sign):
    ret = 0
    for s in state[::-1]:
        ret <<= 1
        if s == sign:
            ret |= 1
    return ret

ans = [INF] * (N + 1)
for state in range(pow(3, N)):
    stateX = 0
    stateY = 0
    M = N
    for _ in range(N):
        state, r = divmod(state, 3)
        stateX <<= 1
        stateY <<= 1
        if r == 0: M -= 1
        if r == 1: stateX |= 1
        if r == 2: stateY |= 1

    cost = 0
    for i in range(N):
        cost += min(costX[stateX][i], costY[stateY][i])

    if ans[M] > cost:
        ans[M] = cost

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

n = int(input())

for s in range(1, n+1):
    ans = 0
    for i in range(1, 101):
        for j in range(1, 101):
            for k in range(1, 101):
                if i*i + j*j + k*k + i*j + j*k + k*i == s:
                    if i == j == k:
                        ans += 1
                    elif i == j != k or j == k != i or k == i != j:
                        ans += 3
                    elif i != j != k:
                        ans += 6
                    break
            else:
                continue
            break
        else:
            continue
        break
    print(ans)
    ans = 0


### FIXED CODE ###

n = int(input())

ans = [0 for _ in range(10001)]

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            s = x*x + y*y + z*z + x*y + y*z + z*x
            if s <= 10000:
                ans[s] += 1

for i in range(1, n+1):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = [int(i) for i in input().split()]
B = sorted(A.copy(), reverse=True)

def divisors():
    for i in range(B[0], 0, -1):
        if any(map(lambda n: n%i==0, B)):
            yield i

ans = 1
divs = divisors()
for d in divs:
    count = 0
    for a in A:
        if a % d != 0:
            count += 1
            if count >= 2:
                break
    if count < 2:
        ans = d
        break

print(ans)

### FIXED CODE ###

# 解けなかった...orz

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

def gcd(i, j):
    if i <= 0:
        return j
    elif j <= 0:
        return i

    while i != j:
        if i < j:
            j %= i
            if j == 0: return i
        else:
            i %= j
            if i == 0: return j
    return i

# M = [0] * N
L = [0] * (N+1)
R = [0] * (N+1)
# L[0] = 0
# R[N] = 0

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

res = max(gcd(L[i], R[i+1]) for i in range(N))
print(res)
### BUGGY CODE ###

t=input();p=input()
[print(i)for i in range(len(t)-len(p)+1)if t[i:].startswith(p)]

### FIXED CODE ###

s=input();t=input()
[print(x) for x in range(len(s)-len(t)+1) if s[x:x+len(t)]==t]
### BUGGY CODE ###

n = int(input())

c = 0
a = 1
i = 1
while c < n:
    s = str(i)
    f = 0
    j=0
    while j < len(s) -1:
        if abs(int(s[j]) - int(s[j+1])) > 1:
            f = 1
            break
        j = j + 1
    if f == 0:
        # print(i)
        c = c + 1
        a = i
    if c == n:
        break
    i += 1

print(a)

### FIXED CODE ###

from collections import deque

n = int(input())

c = 0
q = deque()
for i in range(1, 10):
    q.append(i)

k = 1
while c < n:
    k = q.popleft()
    # print(k)
    if k%10:
        q.append(10*k + k%10 - 1)
    q.append(10 * k + k % 10)
    if k%10 != 9:
        q.append(10*k + (k%10) + 1)
    c += 1

print(k)
### BUGGY CODE ###

nk = list(map(int, input().split()))
n = nk[0]
k = nk[1]
p = list(map(int, input().split()))
p_ = []

for i in range(n-k+1):
    r = 0
    for j in range(k):
        r += p[i+j]

    p_.append(r)

print((max(p_)+k)/2)

### FIXED CODE ###

nk = list(map(int, input().split()))
n = nk[0]
k = nk[1]
p = list(map(int, input().split()))
p_ = []

r = 0
for i in range(k):
    r += p[i]
p_.append(r)

for i in range(k, n):
    r += p[i] - p[i-k]
    p_.append(r)

print((max(p_)+k)/2)
### BUGGY CODE ###

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

result = 0
for i in range(N-1): 
  tmp = 0
  for j in range(i+1, N): 
    tmp += A[j]
  result += tmp * A[i]
print(result%1000000007)

### FIXED CODE ###

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

sum = sum(A)
result = 0

for i in range(N): 
  sum -= A[i]
  result += sum*A[i]

print(result%(10**9+7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [-1 for i in range(N)]
def rec(n):
    if dp[n] == -1:
        if n == 0:
            dp[n] = 0
        elif n == 1:
            dp[n] = abs(h[1]-h[0])
        else:
            work = 10**9
            for i in range(1, K+1):
                if n-i >= 0:
                    temp = rec(n-i)+abs(h[n-i]-h[n])
                    work = work if work<temp else temp
            dp[n] = work
    return dp[n]
print(rec(N-1))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.zeros(N,dtype=int)
for i in range(1, N):
    s=max(0, i-K)
    dp[i] = min(dp[s:i]+abs(h[s:i]-h[i]))
print(dp[-1])
### BUGGY CODE ###

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

ans = 1

for i in range(N):
  ans = ans * a[i]
  
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

if A.count(0) > 0:
  print(0)
else:
  ans = A[0]
  flag = 0
  for i in range(1,N):
    ans *= A[i]
    if ans > 10 ** 18:
      print(-1)
      flag += 1
      break
  if flag == 0:
    print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
r = [[0] * n for _ in range(n)]

p = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if p[a] < h[b]: p[a] = h[b]
    if p[b] < h[a]: p[b] = h[a]

ans = 0
for i in range(n):
    if h[i] > p[i]:
        ans += 1

# print(p)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
 
edeg = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edeg[a].append(b)
    edeg[b].append(a)
 
#print(edeg)

ans = 0
for node in range(n):
    good = True
    for neigber in edeg[node]:
        #print("neigber:", neigber)
        if h[node] <= h[neigber]:
            good = False
    if good:
        ans += 1 

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

from math import factorial
import collections

def fact(n):
    r = 2
    if n - r < 0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

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

for i in range(N):
    balls = BALLS[:i] + BALLS[i+1:]
    print(sum(fact(n) for n in collections.Counter(balls).values()))

### FIXED CODE ###

from math import factorial
import collections

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

MEMO = {}
def fact(n):
    if MEMO.get(n):
        return MEMO[n]
    r = 2
    if n - r < 0:
        MEMO[n] = 0
        return 0
    MEMO[n] = factorial(n) // factorial(r) // factorial(n - r)
    return MEMO[n]

COUNTS = collections.Counter(BALLS)
TOTAL = sum(fact(n) for n in COUNTS.values())

MEMO2 = {}
def solve(n):
    if MEMO2.get(n):
        return MEMO2[n]

    MEMO2[n] = TOTAL - fact(COUNTS[n]) + fact(COUNTS[n] - 1)
    return MEMO2[n]

for i in range(N):
    print(solve(BALLS[i]))
### BUGGY CODE ###

def N(a): #階乗 n!
    ans = 1
    for i in range(1,a+1):
        ans *= i
    return ans

def C(n,k): #組み合わせ nCk
    memo1 = N(n)
    memo2 = N(k)
    memo3 = N(n-k)
    return (memo1)//(memo2*memo3)


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

ans = 0
for i in range(n):
    memo = ans
    ans = max(C(a[n-1],a[i]),ans)
    if ans != memo:
        memo2 = a[i]

print(a[n-1],memo2)

### FIXED CODE ###

def N(a): #階乗 n!
    ans = 1
    for i in range(1,a+1):
        ans *= i
    return ans

def C(n,k): #組み合わせ nCk
    memo1 = N(n)
    memo2 = N(k)
    memo3 = N(n-k)
    return (memo1)//(memo2*memo3)


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

ans = 0
aim = a[n-1]//2

if a[n-1]%2!=0:
    aim2 = a[n-1]//2+1
else:
    aim2 = a[n-1]//2

memo = abs(a[0]-aim)
memo2 = 0
for i in range(n-1):
    if abs(memo) > abs(a[i]-aim):
        memo = abs(a[i]-aim)
        memo2 = a[i]

memo = abs(a[0]-aim2)
memo3 = 0
for i in range(n-1):
    if abs(memo) > abs(a[i]-aim2):
        memo = abs(a[i]-aim2)
        memo3 = a[i]

if abs(memo2-aim) > abs(memo3-aim2):
    ans = memo3
else:
    ans = memo2



print(a[n-1],ans)
### BUGGY CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

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

N = INT()
ans = [0] * N

def fn(x, y, z):
    f = x**2 + y**2 + z**2 + x * y + y * z + z * x
    return f

for n in range(1, N + 1):
    for x in range(1, int(N ** 0.5) + 2):
        for y in range(1, int(N ** 0.5) + 2):
            if fn(x, y, 1) > n:
                break
            for z in range(1, int(N ** 0.5) + 2):
                f = fn(x, y, z)
                if f > n:
                    break
                if f == n:
                    ans[f - 1] += 1

for a in ans:
    print(a)

### FIXED CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

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

N = INT()
ans = [0] * N

def fn(x, y, z):
    f = x**2 + y**2 + z**2 + x * y + y * z + z * x
    return f

for x in range(1, int(N ** 0.5) + 2):
    if fn(x, 1, 1) > N:
        break
    for y in range(1, int(N ** 0.5) + 2):
        if fn(x, y, 1) > N:
            break
        for z in range(1, int(N ** 0.5) + 2):
            f = fn(x, y, z)
            if f > N:
                break
            if f <= N:
                ans[f - 1] += 1

for a in ans:
    print(a)
### BUGGY CODE ###

n =int(input())
s = [input() for i in range(n)]
z = list(set(s))
ans = []
x = 0
for i in z:
    if s.count(i) > x:
        ans.clear()
        ans.append(i)
        x = s.count(i)
    elif s.count(i) == x:
        ans.append(i)
for i in sorted(ans):
    print(i)

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
  s.append(input())
s.sort()
k = 0
f = s
mk = 0
for i in range(n-1):
  if s[i] == s[i+1]:
    k = k+1
    if k == mk :
      mk = k
      f.append(s[i])
    elif k > mk :
      mk = k
      f = [s[i]]
  else:
    k = 0
for i in range(len(f)):
  print(f[i])
### BUGGY CODE ###

from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)



def main():
    K = int(input()) + 1
    ans = 0
    for i in range(1, K):
        for j in range(1, K):
            for k in range(1, K):
                gcd = 1
                mx = min(i, j, k)
                for l in range(2, K):
                    if i % l == 0 and j % l == 0 and k % l == 0:
                        gcd = l
                    if l == mx:
                        break
                ans += gcd
    print(ans)

main()

### FIXED CODE ###

from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)


def main():
    K = int(input()) + 1
    ans = 0
    for i in range(1, K):
        ans += i
        for j in range(i + 1, K):
            def GCD(x, y):
                return GCD(y, x%y) if y else x
            ans += GCD(i, j) * 6
            for k in range(j + 1, K):
                gcd = 1
                mx = min(i, j, k)
                for l in range(2, K):
                    if i % l == 0 and j % l == 0 and k % l == 0:
                        gcd = l
                    if l == mx:
                        break
                ans += gcd * 6
    print(ans)

main()
### BUGGY CODE ###

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


for i in range(n):
    y=[]
    for j in range(n):
        if j!=i:
            y.append(x[j])
    y.sort()
    print(y[n//2-1])


### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
y=x.copy()
y.sort()
cr=y[n//2]
cl=y[n//2-1]

for i in range(n):
    if x[i]<=cl:
        print(cr)
    elif x[i]>=cr:
        print(cl)
### BUGGY CODE ###

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

C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
	L,R = map(int,input().split())
	C[L][R] += 1


D = [[0 for i in range(N+4)] for j in range(N+4)]
for i in range(N+1):
	for j in range(N+1):
		D[i][j+1] = D[i][j] + C[i][j]

buf = []
for j in range(Q):
	p,q = map(int,input().split())
	s = 0
	for i in range(p,q+1):
		s += (D[i][q+1] - D[i][i])
	buf.append(s)
print("\n".join(map(str,buf)))


### FIXED CODE ###

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

C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
	L,R = map(int,input().split())
	C[L][R] += 1


D = [[0 for i in range(N+4)] for j in range(N+4)]
E = [0 for i in range(N+4)]
F = [[0 for i in range(N+4)] for j in range(N+4)]
for i in range(N+1):
	for j in range(N+1):
		D[i][j+1] = D[i][j] + C[i][j]
for i in range(N+1):
	E[i+1] = E[i] + D[i][i]
for i in range(N+2):
	for j in range(N+2):
		F[i+1][j] = F[i][j] + D[i][j]

# C[l][l] + ... + C[l][r] = D[l][r+1] - D[l][l]
# C[i][i] + ... + C[i][r] = D[i][r+1] - D[i][i]
# C[r][r] + ... + C[r][r] = D[r][r+1] - D[r][r]

for j in range(Q):
	p,q = map(int,input().split())
	s = F[q+1][q+1] - F[p][q+1] - (E[q+1] - E[p])
	print(s)
### BUGGY CODE ###

def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))
    arr = []
    ans = []
    for i in range(N):
        arr.append(V[i]-C[i])
    for j in range(1 << N):
        output = []
        for k in range(N):
            if ((j >> k) & 1) == 1:
                output.append(arr[k])
            ans.append(sum(output))
    if max(ans) < 0:
        print(0)
        return
    print(max(ans))
main()

### FIXED CODE ###

def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))
    ans = 0
    for i in range(N):
        ans += max(V[i]-C[i], 0)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def update(i, x):
    while i < n:
        bit[i] += x
        i += i & -i


def getsum(i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


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

Li = -1
Ri = len(x) - 1
i = (Li + Ri) // 2
bit = [0] * (n + 1)
xi = x[i]
for ai, ak in enumerate(a):
    update(ai + 1, (ak > xi) * 2 - 1)
lr = [0] * n

while 1:
    M = 0
    for r in range(n):
        lr[r] = tmp = getsum(r + 1)
        M += (tmp >= 0) * 2 - 1
    for l in range(1, n):
        for r in range(l, n):
            lr[r] = tmp = lr[r] - lr[l - 1]
            M += (tmp >= 0) * 2 - 1
    if M >= 0:
        Li = i
    else:
        Ri = i
    if Li + 1 == Ri: break
    pi = i
    i = (Li + Ri) // 2
    if i < pi:
        s = x[i + 1]
        b = x[pi]
        dt = 2
    else:
        s = x[pi + 1]
        b = x[i]
        dt = -2
    for ai, ak in enumerate(a):
        if s <= ak <= b:
            update(ai + 1, dt)
print(x[Ri])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])
### BUGGY CODE ###

N  = int(raw_input())

ans = []
T, A = [0] * 1000, [0] * 1000

for i in range(N):
    T[i], A[i] = map(int, raw_input().split())

    ans = [T[i], A[i]]

    j = 2

    if i != 0:
        while T[i] < T[i -1] or A[i] < A[i -1]:
            T[i] *= j
            A[i] *= j
            if T[i] < T[i -1] or A[i] < A[i -1]:
                T[i] /= j
                A[i] /= j
            j += 1
        ans = [T[i], A[i]]

print sum(ans)

### FIXED CODE ###

N  = int(raw_input())

ans = [0, 0]
T, A = [0] * 1001, [0] * 1001

for i in range(N):
    T[i], A[i] = map(int, raw_input().split())

    if i != 0 and T[i - 1] - T[i] > 0 or A[i - 1] - A[i] > 0:

        if (T[i  - 1] / T[i]) > (A[i - 1] / A[i]):
            m  = T[i  - 1] / T[i]
            if T[i - 1] % T[i] != 0:
                m += 1 

        else:
            m = A[i - 1] / A[i]
            if A[i - 1] % A[i] != 0:
                m += 1

        T[i] *= m
        A[i] *= m

    ans = [T[i], A[i]]

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

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

for i in range(N-1):
    for j in range(i+1, N):
        ans += A[i] * A[j]
        ans = ans % (1e9 + 7)

print(int(ans))

### FIXED CODE ###

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

ans = 0
mod = int(1e9 + 7)
s = sum(A) % mod

for a in A:
    s -= a
    ans += (a * s) % mod
    ans %= mod

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

import sys
 
input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])
 
extend = A.extend
[extend([BC[i][1]] * BC[i][0]) for i in range(m)]
 
A.sort(reverse=True)
print(sum(A[:n]))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

N, K = map(int, input().split())
while(1):
    tmpN = abs(N-K)
    if tmpN < N:
        N = tmpN
    else:
        break;
print(N)

### FIXED CODE ###

N, K = map(int, input().split())
N = N%K
while(1):
    tmpN = abs(N-K)
    if tmpN < N:
        N = tmpN
    else:
        break;
print(N)