CodeEff/ECCO huggingface dataset:
# Original solution
from heapq import heappush, heappop


def solve():
    N, H = list(map(int, input().split()))
    cut_dmgs = []
    thr_dmgs = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        heappush(cut_dmgs, -a)
        heappush(thr_dmgs, -b)

    ans = 0
    max_cut_dmg = -min(cut_dmgs)
    while thr_dmgs:
        thr_dmg = -heappop(thr_dmgs) 
        if thr_dmg <= max_cut_dmg:
            break
        ans += 1
        H -= thr_dmg
        if H <= 0:
            return ans
    return ans + (H + max_cut_dmg - 1) // max_cut_dmg


print((solve()))


# Optimized solution
N, H, *blades = list(map(int, open(0).read().split()))
cut = max(blades[::2])
throws = sorted(b for b in blades[1::2] if b >= cut)

ans = 0
while throws:
    H -= throws.pop()
    ans += 1
    if H <= 0:
        print(ans)
        exit()

ans += (H + cut - 1) // cut
print(ans)
# Original solution
n,h=list(map(int,input().split()))
A=list(tuple(map(int,input().split())) for i in range(n))
A,B=list(zip(*A))
a=max(A)
count=0
for i in sorted(B)[::-1]:
    if h<=0:break
    elif i>=a:
        count +=1
        h -=i

if h>0:
    count +=(h-1)//a+1

print(count)

# Optimized solution
n,h=list(map(int,input().split()))
A=list(tuple(map(int,input().split())) for i in range(n))
A,B=list(zip(*A))
a=max(A)
count=0
for i in sorted(B)[::-1]:
    if h<=0:break
    elif i>=a:
        count +=1
        h -=i
if h>0:
    if h%a==0:count +=h//a
    else:count +=h//a+1

print(count)
# Original solution
n, h = list(map(int, input().split()))
arr = []
for _ in range(n) :
    a,b = list(map(int, input().split()))
    arr.append((a,-1))
    arr.append((b,1))

arr.sort()
arr.reverse()

cnt = 0
ans = 10**9 + 100
for p in arr :
    if p[1] == -1 :
        # a
        ans = min(ans, cnt + (h+p[0]-1)//p[0])
    elif p[1] == 1 and h>0 :
        # b
        h -= p[0]
        cnt += 1
        if h <= 0 :
            h = 0
            ans = min(ans, cnt)

print(ans)


# Optimized solution
n, h = list(map(int, input().split()))
arr = []
for _ in range(n) :
    a,b = list(map(int, input().split()))
    arr.append((a,-1))
    arr.append((b,1))

arr.sort()
arr.reverse()

cnt = 0
ans = 10**9 + 100
for p in arr :
    if p[1] == -1 :
        # a
        ans = min(ans, cnt + (h+p[0]-1)//p[0])
        break
    elif p[1] == 1 and h>0 :
        # b
        h -= p[0]
        cnt += 1
        if h <= 0 :
            h = 0
            ans = min(ans, cnt)

print(ans)
# Original solution
from math import ceil

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

A, B = [], []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a), B.append(b)
B = sorted(list([x for x in B if x > max(A)]))

count = 0
while H > 0:
    if B:
        H -= B.pop()
    else:
        count += ceil(H / max(A))
        break
    count += 1
print(count)

# Optimized solution
from math import ceil

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

A, B = [], []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a), B.append(b)
max_a = max(A)
B = sorted(list([x for x in B if x > max_a]))

count = 0
while H > 0:
    if B:
        H -= B.pop()
    else:
        count += ceil(H / max_a)
        break
    count += 1
print(count)
# Original solution
def d_katana_thrower(N, H, Swords):
    import math
    # 振ったとき最もダメージが大きい刀以上に投げたときのダメージが大きな刀
    # について、ダメージが大きなものから投げていく。そのダメージの総和が
    # 敵の体力より大きければ投げて倒せばいいし、足りなければ刀を降って倒せばいい。
    # ただし、振る刀の投げダメージが振るより高ければ、投げる前に振らなければならないが、
    # 計算時には「投げてから振る」とみなしても問題ない。
    swing_damage_max = max([s[0] for s in Swords])
    throw_higher_than_swing = [s[1] for s in Swords if s[1] >= swing_damage_max]
    throw_higher_than_swing.sort(reverse=True)

    minimum_moving = 0
    for damage in throw_higher_than_swing:
        if H <= 0:  # 刀を投げている途中で敵を倒したら終わり
            H = 0
            break
        H -= damage
        minimum_moving += 1
    minimum_moving += math.ceil(H / swing_damage_max)
    return minimum_moving

N, H = [int(i) for i in input().split()]
Swords = [[int(i) for i in input().split()] for j in range(N)]
print((d_katana_thrower(N, H, Swords)))

# Optimized solution
def d_katana_thrower():
    # 最大振り火力をもつ刀以上の投げ火力をもつ刀は、大火力のものから順に投げる。
    # 投げダメージの総和が敵の体力より大きければ投げて倒せばいいし、
    # 足りなければ最大振り火力をもつ刀を降り続けて倒せばいい。
    # ただし、最大振り火力をもつ刀については、投げ火力が振り火力より高くても、
    # 投げる前に振らなければならないが、「投げてから振る」とみなして問題ない。
    N, H = [int(i) for i in input().split()]
    Swords = [[int(i) for i in input().split()] for j in range(N)]
    max_swing = max([s[0] for s in Swords])
    sword_to_throw = sorted([s[1] for s in Swords if s[1] >= max_swing], reverse=True)

    threw_times = 0
    for damage in sword_to_throw:
        H -= damage
        threw_times += 1
        if H <= 0:
            return threw_times  # 刀を投げている途中で敵を倒したら終わり
    return threw_times + -(-H // max_swing)

print((d_katana_thrower()))
# Original solution
mina=10**10
def waru(a,b):
  if a%b==0:
    return a//b
  else:
    return (a//b)+1
N,H=list(map(int,input().split()))
A=list()
B=list()
for i in range(N):
  a,b=list(map(int,input().split()))
  A.append(a)
  B.append(b)
sb=sum(B)
for i in range(N):
  S=[k for k in B if k>A[i]]
  n=sum(S)
  if H-n<=0:
    mina=min(mina,len(S))
  else:
    mina=min(mina,waru(H-n,A[i])+len(S))
print(mina)

# Optimized solution
import sys
mina=10**10
def waru(a,b):
  if a%b==0:
    return a//b
  else:
    return (a//b)+1
N,H=list(map(int,input().split()))
A=list()
B=list()
for i in range(N):
  a,b=list(map(int,input().split()))
  A.append(a)
  B.append(b)
ma=max(A)
ind=A.index(ma)
B=[i for i in B if i>ma]
B=sorted(B,reverse=True)
cou=1
s=0
for i in range(len(B)):
  s+=B[i]
  if H<=s:
    print((i+1))
    sys.exit()
H=H-s
print((len(B)+waru(H,ma)))
# Original solution
n, h = [int(t) for t in input().split()]
aa = []
bb = []
for _ in range(n):
    a, b = [int(t) for t in input().split()]
    aa.append(a)
    if b > a:
        bb.append(b)
aa.sort()
bb.sort()

cnt = 0
while h > 0:
    if not bb:
        cnt += (h - 1) // aa[-1] + 1
        break
    elif bb[-1] > aa[-1]:
        h -= bb.pop()
    else:
        h -= aa[-1]
    cnt += 1
print(cnt)


# Optimized solution
n, h = [int(t) for t in input().split()]
aa = []
bb = []
for _ in range(n):
    a, b = [int(t) for t in input().split()]
    aa.append(a)
    if b > a:
        bb.append(b)
aa.sort()
bb.sort()

cnt = 0
while h > 0:
    if not bb or aa[-1] >= bb[-1]:
        cnt += (h - 1) // aa[-1] + 1
        break
    else:
        h -= bb.pop()
    cnt += 1
print(cnt)
# Original solution
import math
N , H = list(map(int , input().split()))
slash = []
throw = []
for _ in range(N):
    a , b = list(map(int , input().split()))
    slash.append(a)
    throw.append(b)
count = 0
#print(slash)
slash_max = max(slash)
#print(throw)
throw.sort(reverse = True)
#print(throw)
while H > 0:
    #print(H)
    if not throw or throw[0] < slash_max :
        count += math.ceil(H / slash_max)
        break
    else:
        H -= throw[0]
        throw.pop(0)
        #print(throw)
    count += 1
print(count)


# Optimized solution
import math

N, H = list(map(int, input().split()))
a_l = []
b_l = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    a_l.append(a)
    b_l.append(b)

a_l.sort(reverse=True)
b_l.sort(reverse=True)
ans = 0
for i in range(N):
    if a_l[0] >= b_l[i]:
        break
    else:
        ans += 1
        H = max(H - b_l[i], 0)
        if H <= 0:
            break
ans += math.ceil(H / a_l[0])
print(ans)
# Original solution
from collections import Counter
from functools import reduce
from itertools import combinations
from operator import xor

n = int(eval(input()))
nodes = [0] * n
for _ in range(n - 1):
    x, y, a = list(map(int, input().split()))
    nodes[x] ^= a
    nodes[y] ^= a

c = Counter(nodes)
ans = 0
remains = set()
for i, v in list(c.items()):
    if i == 0:
        continue
    ans += v // 2
    if v % 2:
        remains.add(i)

for r in (3, 4, 5):
    while True:
        for ns in combinations(remains, r):
            if reduce(xor, ns) == 0:
                remains.difference_update(ns)
                ans += r - 1
                break
        else:
            break
print(ans)


# Optimized solution
from collections import Counter
from functools import reduce
from itertools import combinations
from operator import xor

n = int(eval(input()))
nodes = [0] * n
for _ in range(n - 1):
    x, y, a = list(map(int, input().split()))
    nodes[x] ^= a
    nodes[y] ^= a

c = Counter(nodes)
del c[0]
ans = 0
remains = set()
for i, v in list(c.items()):
    ans += v // 2
    if v % 2:
        remains.add(i)

for r in (3, 4, 5):
    while not r < len(remains) < r * 2:
        for ns in combinations(remains, r):
            if reduce(xor, ns) == 0:
                remains.difference_update(ns)
                ans += r - 1
                break
        else:
            break
print(ans)
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def f(v,i,ans):
    if i == 0:return
    if str(v)[-1] != "0":
        x = int(str(v)+str(int(str(v)[-1])-1))
        ans.add(x)
        f(x,i-1,ans)
    y = int(str(v)+str(v)[-1])
    ans.add(y)
    f(y,i-1,ans)
    if str(v)[-1] != "9":
        z = int(str(v)+str(int(str(v)[-1])+1))
        ans.add(z)
        f(z,i-1,ans)
def main():
    K = int(eval(input()))
    ans = set()
    for i in range(1,10):
        ans.add(i)
        f(i,10,ans)
    ans = list(ans)
    ans.sort()
    print((ans[K-1]))
if __name__ == "__main__":
    main()

# Optimized solution
import sys
input = sys.stdin.readline
from collections import deque
def main():
    K = int(eval(input()))
    que = deque(["1", "2", "3", "4", "5", "6", "7", "8", "9"])
    if K <= 9:
        print((que[K-1]))
    else:
        K -= 9
        while K >= 0:
            v = que.popleft()
            if v[-1] != "0":
                K -= 1
                v1 = v + str(int(v[-1])-1)
                if K == 0:
                    print(v1)
                    break
                que.append(v1)
            K -= 1
            v2 = v + v[-1]
            if K == 0:
                print(v2)
                break
            que.append(v2)
            if v[-1] != "9":
                K -= 1
                v3 = v + str(int(v[-1])+1)
                if K == 0:
                    print(v3)
                    break
                que.append(v3)
if __name__ == "__main__":
    main()
# Original solution
# 再帰的なDFS
def rec(d, val, nums):
    nums.append(val)
    if d == 10:
        return
    
    for delta in (-1, 0, 1):
        add = val % 10 + delta
        if add >= 0 and add <= 9:
            rec(d+1, val * 10 + add, nums)

def main():
    K = int(eval(input()))
    nums = []
    for val in range(1, 10):
        rec(1, val, nums)
    nums.sort()
    print((nums[K-1]))

main()

# Optimized solution
from collections import deque
K = int(eval(input()))
que = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(K):
    num = que.popleft()
    if i == K-1:
        print(num)
        break
    if num%10 == 0:
        que.append(num*10 + num%10)
        que.append(num*10 + num%10 + 1)
    elif num%10 == 9:
        que.append(num*10 + num%10 - 1)
        que.append(num*10 + num%10)
    else:
        que.append(num*10 + num%10 - 1)
        que.append(num*10 + num%10)
        que.append(num*10 + num%10 + 1)
# Original solution
from collections import deque

from heapq import heappush, heappop


def main():
    K = int(eval(input()))

    q = []

    for i in range(1, 10):
        heappush(q, i)

    while True:
        v = heappop(q)
        K -= 1
        if K == 0:
            print(v)
            exit()
        u = v % 10
        nv = v * 10 + u

        heappush(q, nv)
        if u == 0:
            heappush(q, nv + 1)
        elif u == 9:
            heappush(q, nv - 1)
        else:
            heappush(q, nv - 1)
            heappush(q, nv + 1)


main()


# Optimized solution
from collections import deque

from collections import deque


def main():
    K = int(eval(input()))

    q = deque()

    for i in range(1, 10):
        q.append(i)

    while True:
        v = q.popleft()
        K -= 1
        if K == 0:
            print(v)
            exit()
        u = v % 10
        nv = v * 10 + u

        if u == 0:
            q.append(nv)
            q.append(nv + 1)
        elif u == 9:
            q.append(nv - 1)
            q.append(nv)
        else:
            q.append(nv - 1)
            q.append(nv)
            q.append(nv + 1)


main()
# Original solution
K = int(eval(input()))
ans = []
R = [[] for _ in range(11)]
for i in range(1,10):
  R[0].append(i)
for i in range(1,11):
  R[i] = [10**i]
  if i > 1:
    for j in range(i-1):
      for r in R[i-2-j]:
        d = r//(10**(i-2-j))
        if d <= 1:
          R[i].append(10**i+r)
  for r in R[i-1]:
    d = r//(10**(i-1))
    for j in [-1,0,1]:
      if 1<= d+j <= 9:
        R[i].append((d+j)*(10**i)+r)
A = []
#print(sorted(R[0]))
#print(sorted(R[1]))
#print(sorted(R[2]))
#print(sorted(R[3]))
#print(sorted(R[4]))
#print(sorted(R[10]))
for i in range(11):
  for r in R[i]:
    A.append(r)
A.sort()
#print(len(A))
print((A[K-1]))
       
            
            


# Optimized solution
from heapq import heappush, heappop

K = int(eval(input()))
hq = []
for i in range(1,10):
  heappush(hq,i)
cnt = 0
while(cnt < K):
  x = heappop(hq)
  cnt += 1
  for i in [-1,0,1]:
    d = (x%10)+i
    if 0 <= d <= 9:
      heappush(hq,x*10+d)
print(x)
# Original solution
from collections import deque
k=int(eval(input()))
d=deque()
for i in range(1,10): d.append(i)
for i in range(k):
  x=d.popleft()
  if i==k-1:
    print(x)
    break
  if x%10!=0:
    d.append(10*x+x%10-1)
  d.append(10*x+x%10)
  if x%10!=9:
    d.append(10*x+x%10+1)

# Optimized solution
from collections import deque
d=deque(list(range(1,10)))
for i in range(int(eval(input()))):
  x=d.popleft()
  r=x%10;c=x*10+r
  if r!=0:d.append(c-1)
  d.append(c)
  if r!=9:d.append(c+1)
print(x)
# Original solution
k=int(eval(input()))
l=[]
for i1 in range(10):
  l.append(i1)
  for i2 in range(max(i1-1,0),min(i1+2,10)):
    l.append(i1*(10**1)+i2)
    for i3 in range(max(i2-1,0),min(i2+2,10)):
      l.append(i1*(10**2)+i2*(10**1)+i3)
      for i4 in range(max(i3-1,0),min(i3+2,10)):
        l.append(i1*(10**3)+i2*(10**2)+i3*(10**1)+i4)
        for i5 in range(max(i4-1,0),min(i4+2,10)):
          l.append(i1*(10**4)+i2*(10**3)+i3*(10**2)+i4*(10**1)+i5)
          for i6 in range(max(i5-1,0),min(i5+2,10)):
            l.append(i1*(10**5)+i2*(10**4)+i3*(10**3)+i4*(10**2)+i5*(10**1)+i6)
            for i7 in range(max(i6-1,0),min(i6+2,10)):
              l.append(i1*(10**6)+i2*(10**5)+i3*(10**4)+i4*(10**3)+i5*(10**2)+i6*(10**1)+i7)
              for i8 in range(max(i7-1,0),min(i7+2,10)):
                l.append(i1*(10**7)+i2*(10**6)+i3*(10**5)+i4*(10**4)+i5*(10**3)+i6*(10**2)+i7*(10**1)+i8)
                for i9 in range(max(i8-1,0),min(i8+2,10)):
                  l.append(i1*(10**8)+i2*(10**7)+i3*(10**6)+i4*(10**5)+i5*(10**4)+i6*(10**3)+i7*(10**2)+i8*(10**1)+i9)
                  for i10 in range(max(i9-1,0),min(i9+2,10)):
                    l.append(i1*(10**9)+i2*(10**8)+i3*(10**7)+i4*(10**6)+i5*(10**5)+i6*(10**4)+i7*(10**3)+i8*(10**2)+i9*(10**1)+i10)

l=list(set(l))
l.sort()
print((l[k]))

# Optimized solution
import copy
k=int(eval(input()))
ans=[[str(i+1) for i in range(9)]]
l2=[]
for i in range(9):
  l=ans[-1]
  l2=[]
  for j in range(len(l)):
    if int(l[j][-1])!=0:
      l2.append(l[j]+str(int(l[j][-1])-1))
    l2.append(l[j]+str(int(l[j][-1])))
    if int(l[j][-1])!=9:
      l2.append(l[j]+str(int(l[j][-1])+1))
  ans.append(l2)
  l=copy.copy(l2)
a=[]
for i in range(10):
  a=a+ans[i]
print((a[k-1]))
# Original solution
from collections import deque


def main():
    k = int(eval(input()))
    queue = deque([i for i in range(1, 10)])
    pop_time = 0
    now = 1
    while pop_time < k:
        now = queue.popleft()
        if now % 10 != 0:
            queue.append(10 * now + now % 10 - 1)
        queue.append(10 * now + now % 10)
        if now % 10 != 9:
            queue.append(10 * now + now % 10 + 1)
        pop_time += 1
    print(now)


if __name__ == '__main__':
    main()



# Optimized solution
from collections import deque


def main():
    k = int(eval(input()))
    q = deque([i for i in range(1, 10)])
    answer = 0
    for i in range(k):
        now = q.popleft()
        answer = now
        if now % 10 != 0:
            q.append(10 * now + now % 10 - 1)
        q.append(10 * now + now % 10)
        if now % 10 != 9:
            q.append(10 * now + now % 10 + 1)
    print(answer)


if __name__ == '__main__':
    main()
# Original solution
K = int(eval(input()))

V = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range (0, 100000):
	if V[i]%10 == 0:
		V.append(10*V[i]+0)
		V.append(10*V[i]+1)
	elif V[i]%10 == 9:
		V.append(10*V[i]+8)
		V.append(10*V[i]+9)
	else:
		V.append(10*V[i]+V[i]%10-1)
		V.append(10*V[i]+V[i]%10)
		V.append(10*V[i]+V[i]%10+1)

print((V[K-1]))

# Optimized solution
import collections

K = int(eval(input()))

L = [1,2,3,4,5,6,7,8,9]
Q = collections.deque(L)
count = 0 

while count < K-1:
    V = Q.popleft()
    count+=1
    if V%10 == 0:
        Q.append(10*V)
        Q.append(10*V+1)
    elif V%10 == 9:
        Q.append(10*V+8)
        Q.append(10*V+9)
    else:
        Q.append(10*V+(V%10)-1)
        Q.append(10*V+(V%10))
        Q.append(10*V+(V%10)+1)

print((Q.popleft()))
# Original solution
k = int(eval(input()))

def dfs(now, depth):
    STACK.append(str(now))
    if depth == limit:
        LUNLUN.append(int("".join(STACK)))
    else:
        for next in range(now - 1, now + 2):
            if next == -1 or next == 10:
                continue
            dfs(next, depth + 1)
    STACK.pop()

LUNLUN = []
STACK= []
for limit in range(10):
    for i in range(1, 10):
        dfs(i, 0)

print((LUNLUN[k - 1]))


# Optimized solution
k = int(eval(input()))

L = list(range(10))
i = 1
while len(L) <= k:
    Li = L[i]
    a = Li % 10
    for b in range(a - 1, a + 2):
        if b < 0 or b > 9:
            continue
        L.append(Li * 10 + b)
    i += 1

print((L[k]))
# Original solution
k = int(eval(input()))
a=['1','2','3','4','5','6','7','8','9']

while 1:
    if k<=len(a):
        print((a[k-1]))
        exit()
    b=[]
    for i in a:
        if i[-1]!='0':
            b.append(i+chr(ord(i[-1])-1))
        b.append(i+i[-1])
        if i[-1]!='9':
            b.append(i+chr(ord(i[-1])+1))
    k-=len(a)
    a=b.copy()

# Optimized solution
k = int(eval(input()))
a=['1','2','3','4','5','6','7','8','9']

while k>len(a):
    b=[]
    for i in a:
        if i[-1]!='0':
            b.append(i+chr(ord(i[-1])-1))
        b.append(i+i[-1])
        if i[-1]!='9':
            b.append(i+chr(ord(i[-1])+1))
    k-=len(a)
    a=b.copy()

print((a[k-1]))
# Original solution
K = int(eval(input()))

def dfs(d, val, x):
    x.append(val)
    
    if d == 10:
        return
    
    for i in range(-1, 2):
        add = (val % 10) + i
        if 0 <= add <= 9:
            dfs(d + 1, val * 10 + add, x)

x = []
for i in range(1, 10):
    dfs(0, i, x)
print((sorted(x)[K - 1]))


# Optimized solution
from collections import deque

K = int(eval(input()))

q = deque(list(range(1, 10)))
ctr = 0
while ctr < K:
    val = q.popleft()
    ctr += 1
    for i in range(-1, 2):
        add = (val % 10) + i
        if 0 <= add <= 9:
            q.append(val * 10 + add)
            
print(val)
# Original solution

from collections import deque

K = int(eval(input()))
q = deque(list(range(1, 10)))
cnt = 0
ans = 0
while True:
    u = q.popleft()
    cnt += 1
    if cnt == K:
        ans = u
        break

    ll = u % 10
    for i in range(max(0, ll - 1), min(9, ll + 1) + 1):
        q.append(u * 10 + i)

print(ans)


# Optimized solution

from collections import deque

K = int(eval(input()))
q = deque(list(range(1, 10)))
for _ in range(K - 1):
    u = q.popleft()
    n = u % 10
    for x in range(max(0, n - 1), min(9, n + 1) + 1):
        q.append(u * 10 + x)

print((q.popleft()))
# Original solution
from queue import Queue


def solve():

    K = int(eval(input()))

    q = Queue()
    for i in range(9):
        q.put(i+1)
    num = 0
    for i in range(K):
        num = q.get()
        if num % 10 != 0:
            q.put(num*10+num % 10-1)
        q.put(num*10+num % 10)
        if num % 10 != 9:
            q.put(num*10+num % 10+1)
    print(num)


if __name__ == "__main__":
    solve()


# Optimized solution
from collections import deque


def solve():

    K = int(eval(input()))

    dq = deque()
    # 一桁のケース
    for i in range(9):
        dq.append(i+1)

    for i in range(K):
        num = dq.popleft()
        if num % 10 != 0:
            dq.append(num*10+num % 10-1)
        dq.append(num*10+num % 10)
        if num % 10 != 9:
            dq.append(num*10+num % 10+1)

    print(num)


if __name__ == "__main__":
    solve()
# Original solution
maxn = 100005

def solve(n):
	if n<=9:
		return n
	q = [0 for i in range(maxn)]
	front = 1
	rear = 0
	for i in range(1,10):
		rear += 1
		q[rear] = i
	cnt = 9
	while 1:
		u = q[front]
		front += 1
		if u%10 != 0:
			t = u*10 + u%10 -1
			rear += 1
			q[rear] = t
			cnt += 1
			if cnt==n:
				return t
		t = u*10 + u%10
		rear += 1
		q[rear] = t
		cnt += 1
		if cnt==n:
			return t;
		if u%10 != 9:
			t = u*10 + u%10 + 1
			rear += 1
			q[rear] = t
			cnt += 1
			if cnt==n:
				return t

print((solve(int(eval(input())))))    

# Optimized solution
def solve(n):
	if n<=9:
		return n
	q = [0]
	for i in range(1,10):
		q.append(i)
	now = 1
	cnt = 9
	while 1:
		u = q[now]
		now += 1
		if u%10!=0:
			t = u*10 + u%10 - 1
			cnt += 1
			if cnt==n:
				return t
			q.append(t)
		t = u*10 + u%10
		cnt += 1
		if cnt==n:
			return t
		q.append(t)
		if u%10 !=9:
			t = u*10 + u%10 + 1
			cnt += 1
			if cnt==n:
				return t
			q.append(t)

print((solve(int(eval(input())))))
# Original solution
from itertools import product
K = int(eval(input()))
ans = []

for l in range(10):
    for s in range(1, 10):
        for pattern in product([0, 1, 2], repeat=l):  # そのまま, １つ上, １つ下
            X = [s]
            for p in pattern:
                if X[-1] == 0 and p == 2:
                    break
                if X[-1] == 9 and p == 1:
                    break

                if p == 0:
                    X.append(X[-1])

                if p == 1:
                    X.append(X[-1] + 1)

                if p == 2:
                    X.append(X[-1] - 1)
            else:
                ans.append(int(''.join(map(str, X))))

ans.sort()
print((ans[K - 1]))


# Optimized solution
from itertools import product
K = int(eval(input()))

ans = []
for l in range(10):
    for s in range(1, 10):
        for pattern in product([-1, 0, 1], repeat=l):
            X = [s]
            for p in pattern:
                if not (0 <= X[-1] + p <= 9):
                    break
                X.append(X[-1] + p)
            else:
                ans.append(int(''.join(map(str, X))))

ans.sort()
print((ans[K - 1]))
# Original solution
k = int(eval(input()))

numset = {i for i in range(1,10)}
flag = False
count = len(numset)
if count >= k:
    flag = True
arr = [numset]
index = 0

while not flag:
    beforeset = arr[index]
    tmpset = set()
    for i in beforeset:
        tail = str(i)[-1]
        if tail == "0":
            tmpset.add(int(str(i)+str(0)))
            tmpset.add(int(str(i)+str(1)))
        elif tail == "9":
            tmpset.add(int(str(i)+str(8)))
            tmpset.add(int(str(i)+str(9)))
        else:
            tmpset.add(int(str(i)+str(int(tail))))
            tmpset.add(int(str(i)+str(int(tail)+1)))
            tmpset.add(int(str(i)+str(int(tail)-1)))
    count += len(tmpset)
    if count >= k:
        flag = True
    arr.append(tmpset)
    index += 1
    
totalarr = []
for tmpset in arr:
    totalarr += list(tmpset)
    
totalarr.sort()
print((totalarr[k-1]))

# Optimized solution
k = int(eval(input()))

from collections import deque
queue = deque(list(range(1,10)))
count = 0

while count < k:
    tmp = queue.popleft()
    tail = tmp%10
    if tail != 0:
        queue.append(tmp*10+tail-1)
    queue.append(tmp*10+tail)
    if tail != 9:
        queue.append(tmp*10+tail+1)
    count += 1
    
print(tmp)