Harryxun/stf_run huggingface dataset:
K = int(input())

def isRunRun(X):
    x = str(X)
    sa = 0
    for i in range(len(x)-1):
        if abs(int(x[i]) - int(x[i+1])) > 1:
            return False
    return True


if K < 1000:
    num = 1
    count = 0
elif K < 5000:
    num = 110111
    count = 1000
elif K < 10000:
    num = 22111101
    count = 10000


while count < K:
    if isRunRun(num):
        count += 1
    num += 1

print(num-1)

### FIXED CODE ###

# 1行、2変数を受け取るとき
X, Y, Z = map(int, input().split())

print("{} {} {}".format(Z, X, Y))
N=int(input())
A=list(map(int,input().split()))
ans=/A[0]
for i in range(1,N-1):
  ans+=1/A[i]
print(1/ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N):
  ans+=1/A[i]
print(1/ans)
from decimal import Decimal
n=int(input())
ans=0
for in range(n):
    x,y=map(str,input().split())
    if y=="BTC":
        ans+=Decimal(380000*Decimal(x))
    else:
        ans+=Decimal(x)
print(ans)

### FIXED CODE ###

from decimal import Decimal
n=int(input())
ans=0
for i in range(n):
    x,y=map(str,input().split())
    if y=="BTC":
        ans+=Decimal(380000*Decimal(x))
    else:
        ans+=Decimal(x)
print(ans)
from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([-1 if i =="." else i for i in s])

dq = deque()
dq.append((Ch,Cw))
S[Ch][Cw]=0

while dq:
  a=dq.pop()
  if a[0]-1>=0 and (S[a[0]-1][a[1]]==-1 or (S[a[0]-1][a[1]]!="#" and S[a[0]-1][a[1]]>S[a[0]][a[1]])):
    S[a[0]-1][a[1]]=S[a[0]][a[1]]
    dq.appendleft((a[0]-1,a[1]))
  if a[0]+1<H and (S[a[0]+1][a[1]]==-1 or (S[a[0]+1][a[1]]!="#" and S[a[0]+1][a[1]]>S[a[0]][a[1]])):
    S[a[0]+1][a[1]]=S[a[0]][a[1]]
    dq.appendleft((a[0]+1,a[1]))
  if a[1]-1>=0 and (S[a[0]][a[1]-1]==-1 or (S[a[0]][a[1]-1]!="#" and S[a[0]][a[1]-1]>S[a[0]][a[1]])):
    S[a[0]][a[1]-1]=S[a[0]][a[1]]
    dq.appendleft((a[0],a[1]-1))
  if a[1]+1<W and (S[a[0]][a[1]+1]==-1 or (S[a[0]][a[1]+1]!="#" and S[a[0]][a[1]+1]>S[a[0]][a[1]])):
    S[a[0]][a[1]+1]=S[a[0]][a[1]]
    dq.appendleft((a[0],a[1]+1))
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and (S[a[0]-2+i][a[1]-2+j]==-1 or (S[a[0]-2+i][a[1]-2+j]!="#" and S[a[0]-2+i][a[1]-2+j]>=S[a[0]][a[1]]+1)):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]+1
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

### FIXED CODE ###

N,X,T=map(int,input().split())
print(((N-1)//X+1)*T)
import math

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(10**6)
N = int(input())
ans = 0
k = 1
i = 0
while(l[i]**2 <= N):
    if N % (l[i]**k) == 0:
        N //= (l[i]**k)
        k += 1
        ans += 1
    else:
        i += 1
        k = 1
if N != 1 and l[i]!=N:
    ans += 1
print(ans)


### FIXED CODE ###

import math
import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(10**6+10)
N = int(input())
ans = 0
k = 1
i = 0
l2 = []
while(l[i]**2 <= N):
    if N % (l[i]**k) == 0:
        N //= (l[i]**k)
        l2.append(l[i]**k)
        k += 1
        ans += 1
    else:
        i += 1
        k = 1
index = 0
while(index < len(l2)):
    if N % (l2[index]) == 0:
        N //= l2[index]
    else:
        index += 1
if is_prime3(N) and N not in l2:
    ans += 1
print(ans)
#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(100000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  
for some in edge[start_node]:
    d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                e.append((some,new_color))
while d:
    for some in d:
        determine_edge_color(some[0],some[1])
    d=e
    e=deque()
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])

### FIXED CODE ###

#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])
n = int(input())

restrunt=[]

for i in range(n):
    a, b = input().split()
    restrunt.append( {"s":a, "t":int(b), "nom":i+1} )

restrunt.sort(key=lambda res:res["p"], reverse=True)
restrunt.sort(key=lambda res: res["s"])
for res in restrunt:
    print(res["nom"])


### FIXED CODE ###

n = int(input())

restrunt=[]

for i in range(n):
    a, b = input().split()
    restrunt.append( {"s":a, "p":int(b), "nom":i+1} )

restrunt.sort(key=lambda res:res["p"], reverse=True)
restrunt.sort(key=lambda res: res["s"])

for res in restrunt:
    print(res["nom"])
a, b = input()
n = a + b
n = int(n)

if (n ** 0.5).isinteger():
  print(Yes)
else:
  print(No)


### FIXED CODE ###

a, b = input().split(" ")
n = a + b
n = int(n)

if (n ** 0.5).is_integer():
  print('Yes')
else:
  print('No')
S = input()

N = len(S)

cnt_zero = 0
for i in range(N):
  if S[i] == '0':
    cnt += 1
if cnt_zero <= N - cnt_zero:
  print(cnt_zero*2)
else:
  print((N-cnt_zero)*2)

### FIXED CODE ###

S = input()

N = len(S)

cnt_zero = 0
for i in range(N):
  if S[i] == '0':
    cnt_zero += 1
if cnt_zero <= N - cnt_zero:
  print(cnt_zero*2)
else:
  print((N-cnt_zero)*2)
i=0
while 1:
    x = raw_index()
    i = i + 1
    if x == 0:
        break
    print 'Case %s: %s' % (i,x)

### FIXED CODE ###


i=0
while 1:
    x = raw_input()
    if x == "0":
        break
    i = i+1
    print "Case %s: %s" %(i,x)
color = list(map(int,input().split))
print(len(set(color)))

### FIXED CODE ###

color = list(map(int,input().split()))
print(len(set(color)))
a,b,c = map(int,input())

ans = b//c - (a-1)//c
print(ans)

### FIXED CODE ###

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

ans = b//c - (a-1)//c
print(ans)
M, D = map(int,input())
if D<22:
  print(0)
else:
  count = 0
  for i in range(22,D+1):
    d1 = D%10
    d2 = (D-d1)//10
    if d1*d2 <= M:
      count+=1
  print(count)

### FIXED CODE ###

M, D = map(int,input().split())
if D<22:
  print(0)
else:
  count = 0
  for i in range(22,D+1):
    d1 = i%10
    d10 = (i-d1)//10
    if d1>1 and d10>1 and d1*d10 <= M:
      count+=1
  print(count)
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
dic = {}
sets = {0}
for _ in range(M):
  a,b = map(int,input().split())
  if a in sets or b in sets:
    if a in sets and b in sets:
      tmp_a = 0
      tmp_b = 1
      # つなげる処理
      for key in dic.keys():
        if a in dic[key]:
          tmp_a = key
        if b in dic[key]:
          tmp_b = key
      if tmp_a != tmp_b:
        dic[tmp_a].union(dic[tmp_b])
        del dic[tmp_b]
      else:
        dic[tmp_a].add(a)
        dic[tmp_a].add(b)
    else:
      # 入っている方に追加する処理
      for vls in dic.values():
        if a in vls or b in vls:
          vls.add(a)
          vls.add(b)
  else:
    dic[_] = {a,b}
  sets.add(a)
  sets.add(b)

mx = 0

for vals in dic.values():
  mx = max(mx,len(vals))
print(mx)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
 
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
 
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
 
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
 
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
 
n, m = map(int, input().split())
uf = UnionFind(n)
 
for i in range(m):
    a, b = map(int, input().split())
    uf.Unite(a, b)
 
ans = 0
 
for i in range(n):
    ans = max(ans, uf.Count(i))
 
print(ans)
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    a, b, x = map(int, readline().split())

    if a == 0:
        ans = b // x + 1
    else:
        ans = b // x - (a - 1) // x

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, x, *A = map(int, read().split())

    if A[0] > x:
        ans1 = A[0] - x
        prev = x
    else:
        ans1 = 0
        prev = A[0]
    for i in range(1, N):
        if prev + A[i] > x:
            ans1 += prev + A[i] - x
            prev = x - prev
        else:
            prev = A[i]

    if A[-1] > x:
        ans2 = A[-1] - x
        prev = x
    else:
        ans2 = 0
        prev = A[-1]
    for i in range(N - 2, -1, -1):
        if prev + A[i] > x:
            ans2 += prev + A[i] - x
            prev = x - prev
        else:
            prev = A[i]

    print(min(ans1, ans2))
    return


if __name__ == '__main__':
    main()
n = int(input())
s = input()
bc = n*[0]
gc = n*[0]
rc = n*[0]
for i in range(1, n+1):
    mi = n - i
    if s[n - i] == 'B':
        if i == 1:
            bc[mi] = 1
        else:
            bc[mi] = bc[mi+1] + 1
            rc[mi] = rc[mi+1]
            gc[mi] = gc[mi+1]
    elif s[mi] == 'R':
        if i == 1:
            rc[mi] = 1
        else:
            rc[mi] = rc[mi+1] + 1
            bc[mi] = bc[mi+1]
            gc[mi] = gc[mi+1]
    elif s[mi] == 'G':
        if i ==1:
            gc[mi] = 1
        else:
            gc[mi] = gc[mi+1] + 1
            rc[mi] = rc[mi+1]
            bc[mi] = bc[mi+1]
si = 0
for i in range(0, n - 1):
    
    for j in range(i+1, n-1):
        if s[j] != s[i]:
            d = j-i 
            if j+d < n:
                nc = s[j+d]
                if nc in [s[i], s[j]]:
                    l = list(set(['R', 'G', 'B']) - set([s[i], s[j]]))
                    if l[0] == 'R':
                        si+= rc[j+1]
                    elif l[0] == 'G':
                        si += gc[j+1] 
                    else:
                        si += bc[j+1]
                else:
                    l = list(set(['R', 'G', 'B']) - set([s[i], s[j]]))
                    if l[0] == 'R':
                        si+= rc[j+1]-1
                    elif l[0] == 'G':
                        si += gc[j+1] -1
                    else:
                        si += bc[j+1] - 1
            else:
                l = list(set(['R', 'G', 'B']) - set([s[i], s[j]]))
                if l[0] == 'R':
                    si+= rc[j+1]
                elif l[0] == 'G':
                    si += gc[j+1] 
                else:
                    si += bc[j+1]
print(si)

### FIXED CODE ###

n = input()
b = 0
for i in n:
    if i == '7':
        b= 1
        break

if b == 1:
    print("Yes")
else:
    print("No")
import itertools

n,m = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(m)]
ab = [[] for _ in range(n)] 
for i in range(n):
  ab[AB[i][0]-1].append(AB[i][1]-1)
  ab[AB[i][1]-1].append(AB[i][0]-1)

ans = 0
for i in itertools.permutations(range(n), n):
  if i[0] == 0:
    que = i
    cnt = 1
    for k in range(n-1):
      if que[k+1] in ab[que[k]]:
        cnt += 1
    if cnt == n:
      ans += 1

print(ans)

### FIXED CODE ###

import itertools
n,m = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(m)]
a = [0]*n
for x,y in A:
  a[x-1] |= 1<<(y-1)
  a[y-1] |= 1<<(x-1)

def bitdp(n, a):
  dp = [[0]*n for _ in range(1<<n)]
  dp[1][0] = 1
  
  for bit in range(1<<n):
    for v in range(n):
      if bit & 1<<v:
        sub = bit ^ (1<<v)
        
        for u in range(n):
          if (sub & 1<<u) and (a[v] & 1<<u):
            dp[bit][v] += dp[sub][u]
  ans = sum(dp[(1<<n)-1][u] for u in range(1,n))
  return ans

ans = bitdp(n,a)
print(ans)
N = int(input())
list = []
for i in range(N):
    number = int(input())
    if number in list:
        list.remove(number)
        #print(list)
    else:
        list.append(number)
        #print(list)
print(len(list))


### FIXED CODE ###

N = input()
result = "No"
if N[0] == "9":
    result ="Yes"
if N[1] == "9":
    result = "Yes"
print (result)
a=list(map(int,input().split()))
b=[]
c=[1]*(a[0]-1)
for i in range(a[1]):
  b.append(list(map(int,input().split())))
b=sorted(b,key=lambda b:b[1])
for i in range(a[1]):
  if i!=0 and b[i-1][0]>=b[i][0]:
    continue
  if 0 in c[(b[i][0]-1):b[i][1]]:
    continue
  else:
    c[(b[i][1])-2]=0

print(c.count(0))

### FIXED CODE ###

a=list(map(int,input().split()))
out=abs(a[1]-a[0])+abs(a[2]-a[1])
for i in range(3):
    if i ==0:
        b=a[1]
        c=a[2]
    elif i==1:
        b=a[0]
        c=a[2]
    else:
        b=a[0]
        c=a[1]
    if ((abs(b-a[i])+abs(c-b))<out):
        out=abs(b-a[i])+abs(c-b)
    if ((abs(c-a[i])+abs(b-c))<out):
        out=abs(c-a[i])+abs(b-c)
print(out)
n = int(input())
h_L = list(map(int,input().split()))

#dp = [float("inf")] * (10**4 + 1)
dp = [10**8] * 20

dp[0] = 0
dp[1] = abs(h_L[0]-h_L[1])

for i in range(2,n):
    #dp[i]
    # 1
    tmp1 = dp[i-1] + abs(h_L[i-1] - h_L[i])
    dp[i] = min(dp[i],tmp1)
    # 2
    tmp2 = dp[i-2] + abs(h_L[i-2] - h_L[i])
    dp[i] = min(dp[i],tmp2)
#print(dp)
print(dp[len(h_L)-1])

### FIXED CODE ###

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

dp = [10**9] * n
dp[0] = 0
dp[1] = abs(h_L[1] - h_L[0])

for i in range(2,n):
    dp[i] = min(dp[i-1]+abs(h_L[i-1] - h_L[i]),dp[i-2]+abs(h_L[i-2] - h_L[i]))

print(dp[n-1])
import sys
sys.setrecursionlimit(10**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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7


def main(): 
    N, Q = LI()
    STX = []
    for _ in range(N):
        STX.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())

    # セグメント木
    # N: 処理する区間の長さ
    N0 = 2**(N-1).bit_length()
    INF = 2**31-1
    data = [INF]*(2*N0)
    # a_k の値を x に更新
    def update(k, x):
        k += N0-1
        data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            data[k] = min(data[2*k+1], data[2*k+2])
    # 区間[l, r)の最小値
    def query(l, r):
        L = l + N0; R = r + N0
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])

            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    events = []
    construction_number = 0
    for s, t, x in STX:
        events.append((s - x, x, True, construction_number))  # S-X, X, add_flag
        events.append((t - x, x, False, construction_number))  # T-X, X, add_flag
        construction_number += 1

    events.sort()  # O(N log N)
    # D is already sorted by input.

    d = D.pop(0)
    d_num = 0
    ans = [-1] * Q
    for time, x, add_flag, construction_number in events:
        while d < time:
            min_ = query(0, N)
            ans[d_num] = -1 if min_==INF else min_
            d = D.pop(0)
            d_num += 1
        if add_flag:
            update(construction_number, x)
        else:
            update(construction_number, INF)

    for i in ans: print(i)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7

def main(): 
    N, Q = LI()
    STX = []
    for _ in range(N):
        STX.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())

    STX.sort(key=lambda x:x[2])

    ans = [-1] * Q
    skip = [-1] * Q

    from bisect import bisect_left
    for s, t, x in STX:
        left = bisect_left(D, s-x)  # s-x を超える最小のdの位置
        right = bisect_left(D, t-x)  # t-x を超える最小のdの位置

        while left < right:
            if skip[left] == -1:  # 未踏
                ans[left] = x
                skip[left] = right  # つぎにここにきた際は、rightまで見るのをスキップしてよい。
                left += 1
            else:  # 来たことがある
                left = skip[left]  # 以前覚えておいた right まで見るのをスキップする。

    for i in ans: print(i)

main()
a,b,c = list(map(int,input().split()))
cnt = 1

if a == b and b == c:
    cnt += 1
else a<>b and b<>c:
    cnt += 1

if cnt == 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

if a == b and b == c:
    cnt += 1
elif  a != b and b != c and a != c:
    cnt += 1
else:
    pass

if cnt == 1:
    print("Yes")
else:
    print("No")
import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

N = int(input())
S = 0
Y = []
for _ in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b))
    else:
        Y.append((a, b))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

l = 0
r = N
while r - l > 1:
    m = (l+r) // 2
    if S - YY[m] >= 0:
        l = m
    else:
        r = m

a = l * Y[l+1][1] + S - YY[l]
b = N * Y[l+1][1]
g = gcd(a, b)

print(a//g, b//g)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return a

N = int(input())
S = 0
Y = []
for i in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b, b-a, 0))
    else:
        Y.append((a, b, 0, a-b))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

def f(i, n):
    if Y[i][2]:
        return S - YY[n] if n <= i else S - (YY[n+1] - Y[i][0])
    return S - Y[i][3] - YY[n] if n <= i else S - Y[i][3] - (YY[n+1] - Y[i][0])

maa, mab = 0, 1
for i in range(N):
    l = 0
    r = N
    while r - l > 1:
        m = (l+r) // 2
        if f(i, m) >= 0:
            l = m
        else:
            r = m

    a = l * Y[i][1] + min(f(i, l), Y[i][1])
    b = N * Y[i][1]
    if a * mab > b * maa:
        maa, mab = a, b

g = gcd(maa, mab)
print(maa//g, mab//g)
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        if dp[i+1][w-1] != inf:
          a = dp[i+1][w-1]+value[i]
        else:
          a = inf
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w],a)
      else:
        dp[i+1][w]=dp[i][w]
  return dp[N][W]
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
a = knapsack(N,H,weight,value)
 
print(int(a))

### FIXED CODE ###

def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(min(dp[N][H:H+MAX]))