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

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())
n, = map(int,readline().split())
vw = [(0,0)]+[tuple(map(int,readline().split())) for _ in range(n)]

A = 10
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    m = u.bit_length() - A
    if m<0: m=0
    dv = [0]*(1<<m)
    dw = [0]*(1<<m)
    for i in range(m):
        v,w = vw[u]
        for j in range(1<<i):
            dv[j+(1<<i)] = dv[j]+v
            dw[j+(1<<i)] = dw[j]+w
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

        


### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 10
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]

#from itertools import acumulate
for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    #memov[i] = list(accumulate(memov[i],max))
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    #print(lstv,lstw,dv,dw,l)
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    #for j in range(1,len(dv)):
    #    dv[j] = max(dv[j-1],dv[j])
    
    solve(memov[u],memow[u],dv,dw,l)

#print(memov)
#print(memow)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n,k = LI()
    a = [I() - k for _ in range(n)]
    t = []
    ti = 0
    r = 0
    l = 0
    for c in a:
        if c >= 0:
            r += 1
        bi = bisect.bisect_left(t,-c - ti)
        ti += c
        r += l - bi
        bisect.insort_left(t,c-ti)
        l += 1

    return r



print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, n, default, func):
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)

def main():
    n,k = LI()
    a = [I() for _ in range(n)]

    b = [0]
    for i in range(n):
        b.append(b[-1] + a[i] - k)

    d = {}
    for c,i in zip(sorted(set(b)), range(n+1)):
        d[c] = i
    e = [d[c] for c in b]

    l = len(d)

    def f(a,b):
        return a+b

    seg = Seg(l, 0, f)
    for c in e:
        seg.update(c, seg.find(c) + 1)

    r = 0
    for c in e[::-1]:
        t = seg.query(0,c+1)
        r += t-1
        seg.update(c, seg.find(c) - 1)

    return r

print(main())
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
for m in range(n-1):
    d = a[m+1:n]
    e = sum(d)
    b = b + a[m]*e
c = b % (10**9+7)
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 0
d = sum(a)
for m in range(n-1):
    d = d -a[m]
    b = b + a[m]*d
    if b >= 10**9+7:
        b = b % (10**9+7)
print(b)
### BUGGY CODE ###

import sys

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

x,y = map(int,input().split())

MOD = 10**9 + 7

i = x
j = y
if (2*max(x,y) - min(x,y)) % 3 != 0:
	print(0)
	sys.exit()

c1 = (2*max(x,y) - min(x,y)) // 3
c2 = max(x,y) - 2*c1

c1 %= MOD
c2 %= MOD

ans = cmb(c1 + c2 , c1)
print(ans%MOD)


### FIXED CODE ###

import sys

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

x,y = map(int,input().split())

MOD = 10**9 + 7

MAX = max(x,y)
MIN = min(x,y)

if (2*MAX - MIN) % 3 != 0 or MAX / MIN > 2:
	print(0)
	sys.exit()

c1 = (2*MAX - MIN) // 3
c2 = MAX - 2*c1

c1 %= MOD
c2 %= MOD

ans = cmb(c1 + c2 , c1)
print(ans%MOD)
### BUGGY CODE ###

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

ans = 0
mod = 10 ** 9 + 7

for i in range(n):
  for j in range(i+1, n):
    k = (a[i] * a[j]) % mod
    ans += k
    ans %= mod
    
print(ans)

### FIXED CODE ###

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

s = [0 for i in range(n-1)]
s[0] = sum(a) - a[0]
for i in range(1, n-1):
  s[i] = s[i-1] - a[i]

ans = 0
mod = 10 ** 9 + 7

for i in range(n - 1):
  k = a[i] * s[i] % mod
  ans += k
  ans %= mod
    
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
vH = list(map(int, input().split()))

INF = float("inf")
head = [INF,] * (K-1)
vH = head + vH
dp = head + [0,]

for i in range(K, N+K-1):
    dp.append(min(dp[-k] + abs(vH[i] - vH[i-k]) for k in range(1,K+1)))

print(dp[-1])


### FIXED CODE ###

N, K = map(int, input().split())
vH = list(map(int, input().split()))

INF = float("inf")
head = [INF,] * (K-1)
vH = head + vH
dp = head + [0,]

for i in range(K, N+K-1):
    dp.append(min(dp[-k] + abs(vH[i] - vH[i-k]) for k in range(1,K+1)))

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

s=input()
n=len(s)
k=int(input())
lst=list(s)
lst.sort()
ans=[]
for i in range(min(k,n)):
    a=lst[i]
    for j in range(n):
        if s[j]==a:
            for l in range(min(5,n-j)):
                ans.append(s[j:j+l+1])
ans.sort()
t=1
while t<len(ans):
    if ans[t]==ans[t-1]:
        ans.pop(t)
    else:
        t+=1
print(ans[k-1])


### FIXED CODE ###

s=input()
n=len(s)
k=int(input())
lst=list(s)
lst.sort()
ans=[]
for i in range(min(k,n)):
    a=lst[i]
    count=0
    for j in range(n):
        if s[j]==a:
            count+=1
            for l in range(min(5,n-j)):
                ans.append(s[j:j+l+1])
    if count>=5:
        break
ans.sort()
t=1
while t<len(ans):
    if ans[t]==ans[t-1]:
        ans.pop(t)
    else:
        t+=1
print(ans[k-1])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)



## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
def dfs(p,q):
  if p in route[q]:
    route[q].remove(p)
  for r in route[q]:
    cnt[r] += cnt[q]
    dfs(q,r)

dfs(-1,0)
for c in cnt[:-1]:
  print(c,end=" ")
print(cnt[-1])

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict,deque


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
stk = deque([0])
cost = [-1 for _ in range(N)]
cost[0] = cnt[0]
while len(stk) > 0:
  p = stk.pop()
  for q in route[p]:
    if cost[q] >= 0:
      continue
    cost[q] = cost[p] + cnt[q]
    stk.append(q)

print(*cost)
### BUGGY CODE ###

def main():
    n,m = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    ans = [0]*(m)

    l.sort(key = lambda x: x[1],reverse=True)

    for i in range(n):
        a,b = l[i]
        
        for j in range(a-1,m):
            if ans[j] == 0:
                ans[j] = b
                break
    print(sum(ans))

if __name__ == "__main__":
	main()


### FIXED CODE ###

def main():
    import heapq
    n,m = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    q = []
    ans = 0
    now = 0
    for i in range(1,m+1):
        for j in range(now,n):
            if l[j][0] <= i:
                heapq.heappush(q,-l[j][1])
                now = j+1 
            else:
                now = j
                break
        if q:
            ans -= heapq.heappop(q)
       
    print(ans)

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

def update_queue(queue):
    out = queue.pop(0)
    mod10 = out % 10
    if mod10 != 0:
        queue.append(10 * out + mod10 - 1)
    queue.append(10 * out + mod10)
    if mod10 != 9:
        queue.append(10 * out + mod10 + 1)

    return out, queue

N = int(input())
Q = [1,2,3,4,5,6,7,8,9]

for _ in range(N):
    out, Q = update_queue(Q)

print(out)

### FIXED CODE ###

def update_queue(n, queue):
    out = queue[n]
    mod10 = out % 10
    if mod10 != 0:
        queue.append(10 * out + mod10 - 1)
    queue.append(10 * out + mod10)
    if mod10 != 9:
        queue.append(10 * out + mod10 + 1)

    return out, queue

N = int(input())
Q = [1,2,3,4,5,6,7,8,9]

for i in range(N):
    out, Q = update_queue(i, Q)

print(out)
### BUGGY CODE ###

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

for i in range(N):
  for j in range(i+1,N):
    p = A[i]*A[j]
    P += p
    if P >= (10**9+7):
      P %= (10**9+7)
    
sum = P%(10**9+7)
print(sum)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
P = 0
S = sum(A)
m = 10**9+7

for i in range(N):
  S -= A[i]
  P += A[i]*S
  
ans = P%m
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
a = [0] * 2019
a[0] = 1
for i in range(0, n):
  a[(int(s[i : n + 1]) % 2019)] += 1
ans = 0
for i in a:
  ans +=  i * (i - 1) // 2
print(ans)

### FIXED CODE ###

s = input()[::-1]
current = 0
a = [0] * 2019
a[0] = 1
digit = 1
for i in s:
  current += int(i) * digit
  digit *= 10
  digit %= 2019
  current %= 2019
  a[current] += 1
ans = 0
for i in a:
  ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

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

path=[]
for i in range(M):
    a,b=list(map(int,input().split()))
    path.append([a-1,b-1])
    
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.member_num = [1 for _ in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        m1=self.member_num[s1]
        m2=self.member_num[s2]
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.member_num[s1]=m1+m2
                    return [m1,m2]
                else:
                    self.table[s1] = s2
                    self.member_num[s2]=m1+m2
                    return [m1,m2]
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] = -1
                self.table[s2] = s1
                self.member_num[s1] = m1+m2
                return [m1,m2]
        return [0,0]
    
uf=UnionFind(N)

path=path[::-1]
count = 0
ans = [N*(N-1)//2]
for i in range(M):
    a,b=path[i]
    m1,m2 = uf.union(a,b)
    count+=m1*m2
    ans.append(N*(N-1)//2 - count)

ans=ans[:-1]
ans=ans[::-1]

for i in range(M):
    print(ans[i])

### FIXED CODE ###


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

path=[]
for i in range(M):
    a,b=list(map(int,input().split()))
    path.append([a-1,b-1])
    
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.member_num = [1 for _ in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        m1=self.member_num[s1]
        m2=self.member_num[s2]
        if s1 != s2:#根が異なる場合
            if m1 != m2:#グラフの高さが異なる場合
                if m1 < m2:
                    self.table[s1] = s2
                    self.member_num[s2]=m1+m2
                    return [m1,m2]
                else:
                    self.table[s2] = s1
                    self.member_num[s1]=m1+m2
                    return [m1,m2]
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] = -1
                self.table[s2] = s1
                self.member_num[s1] = m1+m2
                return [m1,m2]
        return [0,0]
    
uf=UnionFind(N)

path=path[::-1]
count = 0
ans = [N*(N-1)//2]
for i in range(M):
    a,b=path[i]
    m1,m2 = uf.union(a,b)
    count+=m1*m2
    ans.append(N*(N-1)//2 - count)

ans=ans[:-1]
ans=ans[::-1]

for i in range(M):
    print(ans[i])
### BUGGY CODE ###

import queue

n,m = list(map(int, input().split()))
puted = [0]*(n+1)

ab = [[] for i in range(n+1)]
for i in range(m):
	a,b = list(map(int, input().split()))
	ab[a].append(b)
	ab[b].append(a)

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while -1 in flg or q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]==0:
			flg[i-1]=item
			q.put(i)
			puted[i]=1

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])


### FIXED CODE ###

import queue

n,m = list(map(int, input().split()))
puted = [0]*(n+1)

ab = [[] for i in range(n+1)]
for i in range(m):
	a,b = list(map(int, input().split()))
	ab[a].append(b)
	ab[b].append(a)

q = queue.Queue()
flg = [-1]*n
flg[0] = 0
q.put(1)

while not q.empty():
	item = q.get()
	for i in ab[item]:
		if puted[i]==0:
			flg[i-1]=item
			q.put(i)
			puted[i]=1

if -1 in flg:
	print("No")
	exit()

print("Yes")
for i in range(1,len(flg)):
	print(flg[i])
### BUGGY CODE ###

import sys
import collections

def main():
    N,*S = map(int, open(0).read().split())

    S = sorted(S)

    g = [S.pop(-1)]

    for gen in range(N):
        g.sort(reverse=True)
        for p in g[:2**gen]:
            for si, s in enumerate(S[::-1]):
                if p > s:
                    g.append(s)
                    S.pop(-(si+1))
                    break
            else:
                print('No')
                sys.exit()
    print('Yes')

if __name__=='__main__':
    main()

### FIXED CODE ###

## 他の方と処理内容がほぼ同じなのに何でTLEになるか分からないので、他の方のコードでテスト
N = int(input())
a = list(map(int,input().split(' ')))
a.sort()
    

fathers = [a.pop()]
for _ in range(N):
    sons = list()
    b = list()
    
    for father in fathers:
        while a:
            x = a.pop()
            if father > x:
                sons.append(x)
                break
            else:
                b.append(x)
                
    a = a + b[::-1]
    fathers.extend(sons)
    fathers.sort(reverse = True)
    
    
    
if len(fathers) == 2**N:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

S = input()[::-1]
S_len = len(S)  # <= 200000
ans = 0
dp = [0] * 2019
dp[0] = 1
for i in range(1, S_len+1):
    dp[int(S[:i][::-1]) % 2019] += 1
for i in dp:
    ans += i * (i-1) // 2
print(ans)


### FIXED CODE ###

S = input()[::-1]
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
m = 0
x_10 = 1
for s in S:
    m = (m + int(s) * x_10) % 2019
    dp[m] += 1
    x_10 = (x_10 * 10) % 2019
for i in dp:
    ans += i * (i-1) // 2
print(ans)
### BUGGY CODE ###

def main():

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

    import collections

    c = collections.Counter(a).most_common()

    m = 10**9 + 7
    ans = 0
    for i in range(0,len(c)):
        num1 = c[i][0]
        cnt1 = c[i][1]
        if cnt1 != 1:
            tmp = (num1**2) % m
            ans +=  tmp * ((cnt1 * (cnt1 - 1) ) // 2)
        for j in range(i+1, len(c)):
            num2 = c[j][0]
            cnt2 = c[j][1]
            tmp = (num1 * num2) % m
            ans += tmp * (cnt1 * cnt2)

    print(ans%m)

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():

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


    m = 10**9 + 7
    ans = 0
    s = []
    total = sum(a)
    s.append(total-a[0])
    for i in range(1,n):
        s.append(s[i-1] - a[i])
    for i in range(n):
        tmp = s[i] % m
        ans += tmp * a[i]
    # ans //= 2
    print(ans%m)

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

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

    min_diff = float('inf')
    for i in range(1,N):
        if min_diff > abs(sum(a[i:])-sum(a[:i])):
            min_diff = abs(sum(a[i:])-sum(a[:i]))

    print(min_diff)

main()

### FIXED CODE ###

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

    sum_a = sum(a)
    min_diff = float('inf')
    sum_first = 0
    for i in range(N-1):
        sum_first += a[i]
        if min_diff > abs(sum_a - 2 * sum_first):
            min_diff = abs(sum_a - 2 * sum_first)

    print(min_diff)

main()
### BUGGY CODE ###

n=int(input())
t,a=map(int,input().split())
for i in range(n-1):
    ti,ai=map(int,input().split())
    tii,aii,m=ti,ai,1
    while tii*m < t or aii*m < a:
        m+=1
    t,a=tii*m,aii*m
print(t+a)


### FIXED CODE ###

import math
n=int(input())
t,a=1,1
for i in range(n):
    ti,ai=map(int,input().split())
    m=max(math.ceil(t/ti), math.ceil(a/ai))
    while t > ti*m or a > ai*m:
        m+=1
    while t <= ti*(m-1) and a <= ai*(m-1):
        m-=1
    t,a=ti*m,ai*m
print(t+a)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1 = A.count(1)
    n2 = A.count(2)
    n3 = A.count(3)

    dp = [[[-1.0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 0

    def solve(n1, n2, n3):

        if dp[n1][n2][n3] >= 0:
            return dp[n1][n2][n3]

        cnt = n1 + n2 + n3
        ret = 0
        if n3 >= 1:
            ret += solve(n1, n2 + 1, n3 - 1) * n3
        if n2 >= 1:
            ret += solve(n1 + 1, n2 - 1, n3) * n2
        if n1 >= 1:
            ret += solve(n1 - 1, n2, n3) * n1

        ret = (ret + N) / cnt
        dp[n1][n2][n3] = ret
        return ret

    print(solve(n1, n2, n3))


if __name__ == '__main__':
    main()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

people_num, first_point, correct = map(int,input().split())
who_correct = [input() for i in range(correct)]
points = [first_point for i in range(people_num)]

for i in range(correct):
  for j in range(people_num):
    if j != int(who_correct[i])-1:
      points[j] -= 1
      if points[j] == 0:
        points[j] = - 100000000

for i in range(people_num):
  if points[i] < 0:
  	print("No")
  else:
    print("Yes")

### FIXED CODE ###

people_num, first_point, correct = map(int,input().split())
who_correct = [input() for i in range(correct)]
points = [first_point-correct for i in range(people_num)]

 
for i in range(correct):
    points[int(who_correct[i])-1] += 1
    
for i in range(people_num):
  if points[i] <= 0:
  	print("No")
  else:
    print("Yes")