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

#入力受け取りの高速化、しなくてもよい
#但し文字列のまま扱うときは注意、例えば . は46として、 # は35として扱われる
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
#ここまでが高速化
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=inputs()
#0 based index (0始まり)にする
nx-=1;ny-=1;gx-=1;gy-=1
from collections import deque
#dqが徒歩、2が魔法での移動を入れる
dq=deque([(nx,ny)])
dq2=deque([])
#かかるコストを保存しておく
T=[[float('inf')]*w for  a in range(h)]
#初期値は0で、スタート地点に保存
T[nx][ny]=0
#徒歩でのx,yの差分
moves=((1,0),(-1,0),(0,1),(0,-1))
from itertools import product as pr
#魔法での移動の差分、tuple( (i,j) |-2<=i,j<=2かつ(i,j)!=(0,0)  )と等価
Mmoves=tuple(i for i in pr((-2,-1,0,1,2),repeat=2)if i!=(0,0) )

while dq:
    #先に徒歩で行けるだけ行きたいので、徒歩を使い切るまでは魔法で行った地点たちに手を出さない
    while dq:
        x,y=dq.popleft()
        for i,j in moves:
            nex,ney=x+i,y+j
            #盤面の外や壁にぶつかるのは除外
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]<T[nex][ney]:
                #コストを更新できるなら改めて捜査
                T[nex][ney]=T[x][y]
                dq.append((nex,ney))
        for i,j in Mmoves:
            nex,ney=x+i,y+j
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]+1<T[nex][ney]:
                T[nex][ney]=T[x][y]+1
                dq2.append((nex,ney))
    #徒歩で行ける地点を使い切ったので、今度は魔法で行ける地点を捜査
    dq,dq2=dq2,dq
if T[gx][gy]==float('inf'):print(-1)
else:print(T[gx][gy])


### FIXED CODE ###

#入力受け取りの高速化、しなくてもよい
#但し文字列のまま扱うときは注意、例えば . は46として、 # は35として扱われる
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
#ここまでが高速化
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=inputs()
#0 based index (0始まり)にする
nx-=1;ny-=1;gx-=1;gy-=1
from collections import deque
#dqが徒歩、2が魔法での移動を入れる
dq=deque([(nx,ny)])
dq2=deque([])
#かかるコストを保存しておく
T=[[float('inf')]*w for  a in range(h)]
#初期値は0で、スタート地点に保存
T[nx][ny]=0
#徒歩でのx,yの差分
moves=((1,0),(-1,0),(0,1),(0,-1))
from itertools import product as pr
#魔法での移動の差分、tuple( (i,j) |-2<=i,j<=2かつ(i,j)!=(0,0)  )と等価
Mmoves=tuple(i for i in pr((-2,-1,0,1,2),repeat=2)if i!=(0,0) )

while dq:
    #先に徒歩で行けるだけ行きたいので、徒歩を使い切るまでは魔法で行った地点たちに手を出さない
    while dq:
        x,y=dq.popleft()
        for i,j in moves:
            nex,ney=x+i,y+j
            #盤面の外や壁にぶつかるのは除外
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]<T[nex][ney]:
                #コストを更新できるなら改めて捜査
                T[nex][ney]=T[x][y]
                dq.append((nex,ney))
        for i,j in Mmoves:
            nex,ney=x+i,y+j
            if not(0<=nex<h and 0<=ney<w) or maze[nex][ney]==35:continue
            if T[x][y]+1<T[nex][ney]:
                T[nex][ney]=T[x][y]+1
                dq2.append((nex,ney))
    #徒歩で行ける地点を使い切ったので、今度は魔法で行ける地点を捜査
    dq,dq2=dq2,dq
if T[gx][gy]==float('inf'):print(-1)
else:print(T[gx][gy])
### BUGGY 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)
def rec(n):
    if dp[n] == 0:
        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(int(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 ###

from itertools import accumulate
import sys
sdin = sys.stdin.readline

n,m,q = map(int, sdin().split())

lr = []
for i in range(m):
    l,r = map(int, sdin().split())
    lr.append(tuple([l-1, r-1]))
        
pq = []
for _ in range(q):
    p,q = map(int, sdin().split())
    pq.append(tuple([p-1, q-1]))


# n×nフィールドを用意して各列車のl,r点をプロット
field = [[0 for _ in range(n)] for _ in range(n)]
for l, r in lr:
    field[l][r] += 1
    
# fieldのx方向の累積和を取る
field_cum = [list(accumulate(field[i])) for i in range(n)]    

# 各クエリに対し、rがpからqの間に入っているものを足し合わせる
for p,q in pq:
    ans = 0
    for i in range(p,q+1):
        ans += field_cum[i][q]
    print(ans)

### FIXED CODE ###

from itertools import accumulate
import sys
sdin = sys.stdin.readline

n,m,q = map(int, sdin().split())

lr = []
for i in range(m):
    l,r = map(int, sdin().split())
    lr.append(tuple([l-1, r-1]))
        
pq = []
for _ in range(q):
    p,q = map(int, sdin().split())
    pq.append(tuple([p-1, q-1]))


# n×nフィールドを用意して各列車のl,r点をプロット
field = [[0 for _ in range(n)] for _ in range(n)]
for l, r in lr:
    field[l][r] += 1
    
# fieldのx方向の累積和を取る
field_cum = [list(accumulate(field[i])) for i in range(n)]    

# 各クエリに対し、rがpからqの間に入っているものを足し合わせる
for p,q in pq:
    ans = 0
    for i in range(p,q+1):
        ans += field_cum[i][q]
    print(ans)
### BUGGY CODE ###

S = input()
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
# dp[i][j] は頭からi番目までの数字を13で割った時j余る数がいくつあるか
MOD = 10**9 + 7

dp[0][0] = 1 # 何もなしのとき０とする

"""
たとえば５６７８という数字について考えるとき
5：s[1][5] = 1で他のjが０
56：5 -> 56なので、 dp[2][(5*10 + 6) % 13] += dp[1][5]
先頭からi文字目まで見たときに余りが５となる数字列について、一桁増えると余りも一桁増える＆新たに増えた桁との和のさらにあまりが新たにできた数字の余り
"""

for i in range(1, len(S)+1):
    if S[i-1] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k*10 + j) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく
    else:
        for k in range(13):
            dp[i][(k*10 + int(S[i-1])) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく

print(dp[-1][5] % MOD)

### FIXED CODE ###

"""
この解答に自分用にコメントつけただけ
https://atcoder.jp/contests/abc135/submissions/6585300
"""

def main():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
    # dp[i][j] は頭からi番目までの数字を13で割った時j余る数がいくつあるか
    MOD = 10**9 + 7

    dp[0][0] = 1 # 何もなしのとき０とする

    """
    たとえば５６７８という数字について考えるとき
    5：s[1][5] = 1で他のjが０
    56：5 -> 56なので、 dp[2][(5*10 + 6) % 13] += dp[1][5]
    先頭からi文字目まで見たときに余りが５となる数字列について、一桁増えると余りも一桁増える＆新たに増えた桁との和のさらにあまりが新たにできた数字の余り
    """

    for i in range(1, len(S)+1):
        if S[i-1] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i][(k*10 + j) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく
        else:
            for k in range(13):
                dp[i][(k*10 + int(S[i-1])) % 13] += dp[i-1][k] % MOD # 足し合わせなのでMODとっておく

    print(dp[-1][5] % MOD)

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


n = int(input())

cnt = 0
for a in range(n-1):
    for b in range(n-1):
        for c in range(n-1):
            if (a+1) * (b+1) + (c+1) == n :
                cnt += 1
            
print(cnt)

### FIXED CODE ###



n = int(input())
cnt = 0
for i in range(1,n):
    cnt += int((n-1)/i)
            
print(cnt)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

# dp[i][j] := iからとjから始めた時に、一致する最大の長さ
dp = list2d(N+1, N+1, 0)
# 後ろから埋めていく
for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

mx = 0
for i in range(N+1):
    for j in range(N+1):
        # 最大値更新の際は、iとjがその値以上離れていることを確認する
        if dp[i][j] > mx and abs(i-j) >= dp[i][j]:
            mx = dp[i][j]
print(mx)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        # 各文字を数値に変換しておく
        S = [ord(s)-97 for s in S]

        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        # ハッシュの生成
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    # 区間[i,j)のハッシュ値を取得
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    A = {}
    for i in range(N-m+1):
        a_hash = rh.get(i, i+m)
        if a_hash in A:
            # a_hashが2回目以降に出現したindex
            j = A[a_hash]
            # iとjがm以上離れているかどうか
            if i-j >= m:
                return True
        else:
            # a_hashが最初に出現したindex
            A[a_hash] = i
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))
### BUGGY CODE ###

from numba import njit

@njit(cache=True)
def calc(N, M, A, X, Y):
    ans = 0
    for a in A:
        aa = (a // N + 1) * M + a % N + 1
        ans += X[aa]
        h = X[aa]
        if h < 0: continue
        Q = [(aa, h)]
        q = 0
        X[aa] -= 1
        Y[aa] = 0
        dd = (-1, 1, M, -M)
        while q < len(Q):
            i, h = Q[q]
            q += 1
            for d in dd:
                j = i + d
                y = Y[j]
                if X[j] >= h + y:
                    X[j] -= 1
                    Q.append((j, h + y))
    return ans

N = int(input())
A = [int(a)-1 for a in input().split()]
M = N + 2
X = [max(min(i-1, j-1, M-2-i, M-2-j), -1) for j in range(M) for i in range(M)]
Y = [min(x, 0) + 1 for x in X]

print(calc(N, M, A, X, Y))


### FIXED CODE ###

from collections import deque
N = int(input())
A = [int(a)-1 for a in input().split()]
M = N + 2
X = [max(min(i-1, j-1, M-2-i, M-2-j), -1) for j in range(M) for i in range(M)]
Y = [min(x, 0) + 1 for x in X]

def calc(i0):
    h = X[i0]
    if h < 0: return
    Q = deque([(i0, h)])
    X[i0] -= 1
    Y[i0] = 0
    dd = (-1, 1, M, -M)
    while Q:
        i, h = deque.popleft(Q)
        for d in dd:
            j = i + d
            y = Y[j]
            if X[j] >= h + y:
                X[j] -= 1
                deque.append(Q, (j, h + y))
ans = 0
for a in A:
    aa = (a // N + 1) * M + a % N + 1
    ans += X[aa]
    calc(aa)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
tree=[[] for i in range(n+1)]
parent=[0]*(n+1)
count=[0]*m
for i in range(1,m+1):
    a,b=ab[-i]
    if parent[a]==0 and parent[b]==0:
        parent[a]=a
        parent[b]=a
        tree[a].append(b)
        count[-i]=1
    elif parent[a]==0:
        count[-i]=len(tree[parent[b]])+1
        parent[a]=parent[b]
        tree[parent[b]].append(a)
    elif parent[b]==0:
        count[-i]=len(tree[parent[a]])+1
        parent[b]=parent[a]
        tree[parent[a]].append(b)
    elif parent[a]==parent[b]:
        count[-i]=0
    else:
        A=parent[a]
        B=parent[b]
        count[-i]=(len(tree[A])+1)*(len(tree[B])+1)   
        for u in tree[B]:
            parent[u]=A
        parent[B]=A
        tree[A].append(B)
        tree[A]+=tree[B]
        tree[B]=[]
sum=0
for i in range(0,m):
    sum+=count[i]
    print(sum)

### FIXED CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
tree=[[] for i in range(n+1)]
parent=[0]*(n+1)
count=[0]*m
for i in range(1,m+1):
    a,b=ab[-i]
    A=parent[a]
    B=parent[b]
    if A==0 and B==0:
        parent[a]=a
        parent[b]=a
        tree[a].append(b)
        count[-i]=1
    elif A==0:
        count[-i]=len(tree[B])+1
        parent[a]=B
        tree[B].append(a)
    elif B==0:
        count[-i]=len(tree[A])+1
        parent[b]=A
        tree[A].append(b)
    elif parent[a]==parent[b]:
        count[-i]=0
    else:
        A=parent[a]
        B=parent[b]
        u=len(tree[A])
        v=len(tree[B])
        count[-i]=(u+1)*(v+1)   
        if u<v:
            A,B=B,A
            a,b=b,a
        for u in tree[B]:
            parent[u]=A
        parent[B]=A
        tree[A].append(B)
        tree[A]+=tree[B]
        tree[B]=[]
sum=0
for i in range(0,m):
    sum+=count[i]
    print(sum)
### BUGGY CODE ###

class work(object):
    def __init__(self, nums):
        self.a = nums[0]
        self.b = nums[1]
        self.is_used = False

    def __repr__(self):
        return "({}, {})".format(self.a, self.b)

    def __lt__(self, other):
        if self.a == other.a:
            return self.b > other.b
        return self.a < other.a


(n, m) = map(int, input().split())
works = []
for _ in range(n):
    works.append(work(list(map(int, input().split()))))
sorted_works = sorted(works)

sum = 0
for i in range(1, m + 1):
    index = 0
    for j, w in enumerate(sorted_works):
        if i < w.a:
            break
        index += 1
    if 0 == index:
        continue
    max_index = 0
    max_reward = 0
    for j in range(index):
        if (not sorted_works[j].is_used) and (max_reward < sorted_works[j].b):
            max_index = j
            max_reward = sorted_works[j].b
    sum += max_reward
    sorted_works[max_index].is_used = True

print(sum)


### FIXED CODE ###

import heapq

(n, m) = map(int, input().split())
jobs = {}
for _ in range(n):
    (a, b) = map(int, input().split())
    if not a in jobs:
        jobs[a] = []
    jobs[a].append(-b)

heap = []
sum = 0
for i in range(1, m + 1):
    if i in jobs:
        for j in jobs[i]:
            heapq.heappush(heap, j)
    if 0 < len(heap):
        sum -= heapq.heappop(heap)
print(sum)
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())

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

heapq.heapify(aa)

for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        tmp = heapq.heappop(aa)
        heapq.heappush(aa, max(tmp, c))
        if tmp >= c:
            break

print(sum(aa))

### FIXED CODE ###

n, m = map(int, input().split())

from collections import defaultdict

cb = defaultdict(int)

for a in input().split():
    cb[int(a)] += 1

for _ in range(m):
    b, c = map(int, input().split())
    cb[c] += b

cbl = sorted(cb.items())

res = n

ans = 0

while res > 0:
    c, b = cbl.pop()
    ncount = min(res, b)
    ans += c * ncount
    res -= ncount

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

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

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

if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
  
for i in range(2, n+1):
  if i in a:
    dp[i] = 0
  else:
    dp[i] = dp[i-1] + dp[i-2]
  
print(dp[n]%1000000007)

### FIXED CODE ###

n, m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]
a.append(0)

dp = [0] * (n+1)
dp[0] = 1
acounter = 0
if a[0] == 1:
  dp[1] = 0
  acounter = 1
else:
  dp[1] = 1

for i in range(2, n+1):
  if i == a[acounter]:
    dp[i]=0
    acounter+=1
  else:
    dp[i] = (dp[i-1]%1000000007 + dp[i-2]%1000000007)%1000000007
  
print(dp[n]%1000000007)
### BUGGY CODE ###

#!/user/bin/env python
#pythonプログラムであることを示している

# -*- coding: utf-8 -*-
"""
このプログラムはPythonを書く際のテンプレとなっています。これをコピペしてコーディングを行なってください。
なお字下げしないこと！！
"""

__author_ = 'Maruta Yuzuha'
__version_ = '1.0.0'
__date__ = '2019/12/25'

def main():
    """
    ここでプログラムの解説を行う
     >>main()
    Hello world.
    0
    """
    s = input().split()
    t = input().split()
    for i in range(int(s[0])):
        t[i] = int(t[i])
    a = 0  #勝つまでの回数
    c = sum(t)
    d = int(s[1])
    for i in range(int(s[1])):
        if sum(t) != 0:
            if d != 0:
                c -= max(t)
                for j in range(int(s[0])):
                    if max(t) == t[j]:
                        t[j] = 0
                d -= 1
            else:
                break
    
    print(a+sum(t))
    return 0

if __name__ == '__main__':
    #上記のifの記述によってこのスクリプトファイルが起動された時だけ実行する部分になる。
    #ちなみにスクリプトが "モジュールとして"インポートされた時には実行されない、

    #単体テスト:モジュールのdocstring(ドキュメンテーション文字列)に記載された全ての対話実行例が書かれている通りに動作するかを確認
    #python ファイル名 -v
    import doctest
    doctest.testmod()

    #実際にmain()を呼び出して、結果を得て、その結果でPythonシステムを終える
    import sys
    sys.exit(main())

### FIXED CODE ###

#!/user/bin/env python
#pythonプログラムであることを示している

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

def main():
    """
    ここでプログラムの解説を行う
     >>main()
    Hello world.
    0
    """
    s = list(map(int, input().split()))
    t = list(map(int, input().split()))
    t.sort(reverse=True)
    a = 0  #勝つまでの回数
    b = s[0]#何匹か
    d = s[1]#必殺技の回数
    f = 0# Maxのいち
    # for j in range(d):  #必殺技の回数
    #     c = sum(t)
    #     if c != 0:
    #         g = max(t)
    #         for i in range(b):
    #             if g == t[i]:
    #                 t[i] = 0
    #                 break
    #         t[f] = 0
    #         f = 0
    #     else:
    #         break
    c = sum(t)
    for i in range(d):
        if c != 0:
            c -= t[i]
            t[i] = 0
        else:
            break
    a += sum(t)
    print(a)
    return 0

if __name__ == '__main__':

    #実際にmain()を呼び出して、結果を得て、その結果でPythonシステムを終える
    import sys
    sys.exit(main())
### BUGGY CODE ###

#!/usr/bin/env python3

import collections

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

c = collections.Counter(A)
values, counts = zip(*c.most_common())

ans = 0
for i in range(len(values)):
    tmp = counts[i]
    ans += (tmp * (tmp-1))//2

for i in range(N):
    num = A[i]
    index = values.index(num)
    print(ans - counts[index] + 1)


### FIXED CODE ###

#!/usr/bin/env python3

import collections

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

c = collections.Counter(A)
values = c.keys()
counts = c.values()

subs = {}
a_sum = 0
for v, c in zip(values, counts):
    subs[v] = c
    a_sum += (c * (c-1)) // 2

for i in range(N):
    print(a_sum - subs[A[i]] + 1)
### BUGGY CODE ###

import fractions

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


T = 1 # 高橋くんの最小得票数
A = 1 # 青木くんの最小得票数
ans = 2

for i in range(0, N):
    T_tmp = TA[i][0]
    A_tmp = TA[i][1]
    while T_tmp < T or A_tmp < A:
        T_tmp += TA[i][0]
        A_tmp += TA[i][1]
    T = T_tmp
    A = A_tmp
    ans = T + A

print(ans)


### FIXED CODE ###

import math

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


T = 1 # 高橋くんの最小得票数
A = 1 # 青木くんの最小得票数
ans = 2

for i in range(0, N):
    #m = max(math.ceil(T / TA[i][0]), math.ceil(A / TA[i][1]))
    m = max(-(-T // TA[i][0]), -(-A // TA[i][1]))
    T = TA[i][0] * m
    A = TA[i][1] * m
    ans = T + A

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

from math import ceil
# from decimal import Decimal

N, K = map(int, input().split())
A = list(map(int, input().split()))
# N, K = 2*10**5, 1
# A = [10**9]*N

def solve(x):
    m = 0
    for a in A:
        m += a//x - (a%x == 0)
    # print(x, m)
    return m <= K

A = [a*10**10 for a in A]

ok, ng = max(A), 0
while abs(ok-ng > 1):
    mid = (ok+ng)//2
    # print(mid)
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(-(-mid//10**10))

### FIXED CODE ###

BIG = 10**10

N, K = map(int, input().split())
A = list(map(int, input().split()))
# N, K = 2*10**5, 2*10**5
# A = [10**9]*N

def solve(x):
    m = 0
    for a in A:
        m += -(-(a//x))
    # print(x, m)
    return m > K

A = [a*BIG for a in A]

# c = 0
ok, ng = 0, max(A)
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    # print(mid)
    if solve(mid):
        ok = mid
    else:
        ng = mid
    # c += 1

# print(c)

print(-(-ok//BIG))
### BUGGY CODE ###

import copy

def main():
    n = int(input())
    a = list( map( int, input().split()))
    sum = 1
    if 0 in a:
        print(0)
    else:
        for i in a:
            sum = sum * i
        if sum > 1000000000000000000:
                print(-1)
                exit()
        else:
            print(sum)
    
if __name__ == '__main__':
    main()
   


### FIXED CODE ###

import copy

def main():
    n = int(input())
    a = list( map( int, input().split()))
    sum = 1
    if 0 in a:
        print(0)
    else:
        for i in a:
            sum = sum * i
            if sum > 1000000000000000000:
                print(-1)
                exit()
        print(sum)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]
tmp=len(ansListab)
for i in range(tmp):
  for j in range(z):
    ansList.append(ansListab[i]+c[j])

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])


### FIXED CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])