Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Time Limit Exceeded

Solution code:
d={0: 0, 50: 232, 100: 878, 150: 2321, 200: 4445, 250: 6655, 300: 8788, 350: 11112, 400: 21122, 450: 23333, 500: 33322, 550: 43232, 600: 45434, 650: 54566, 700: 56776, 750: 66678, 800: 76667, 850: 78878, 900: 88888, 950: 99898, 1000: 110111, 1050: 112343, 1100: 122345, 1150: 211112, 1200: 221122, 1250: 223333, 1300: 233322, 1350: 321101, 1400: 323234, 1450: 333223, 1500: 343211, 1550: 344565, 1600: 432332, 1650: 434456, 1700: 444444, 1750: 454432, 1800: 456556, 1850: 544322, 1900: 545676, 1950: 555656, 2000: 565566, 2050: 567776, 2100: 655543, 2150: 665445, 2200: 667655, 2250: 676788, 2300: 765432, 2350: 766778, 2400: 776767, 2450: 778987, 2500: 788989, 2550: 877677, 2600: 887765, 2650: 889998, 2700: 987777, 2750: 998767, 2800: 1001012, 2850: 1011232, 2900: 1101111, 2950: 1112101, 3000: 1122111, 3050: 1210000, 3100: 1212233, 3150: 1222321, 3200: 1232232, 3250: 1234434, 3300: 2101234, 3350: 2112232, 3400: 2122234, 3450: 2211000, 3500: 2221010, 3550: 2223222, 3600: 2233211, 3650: 2234565, 3700: 2322345, 3750: 2332334, 3800: 2334544, 3850: 2344454, 3900: 3210122, 3950: 3221000, 4000: 3223212, 4050: 3232345, 4100: 3234555, 4150: 3322343, 4200: 3332332, 4250: 3334456, 4300: 3344444, 4350: 3432211, 4400: 3434343, 4450: 3444323, 4500: 3445677, 4550: 3455665, 4600: 4321222, 4650: 4323433, 4700: 4333344, 4750: 4343332, 4800: 4345456, 4850: 4433223, 4900: 4443211, 4950: 4444565, 5000: 4454545, 5050: 4456677, 5100: 4544443, 5150: 4554345, 5200: 4556555, 5250: 4566543, 5300: 4567889, 5350: 5433443, 5400: 5443345, 5450: 5445555, 5500: 5455543, 5550: 5543223, 5600: 5545433, 5650: 5554565, 5700: 5556767, 5750: 5566677, 5800: 5654444, 5850: 5656654, 5900: 5666556, 5950: 5676545, 6000: 5677899, 6050: 6544321, 6100: 6545667, 6150: 6555655, 6200: 6565565, 6250: 6567767, 6300: 6655456, 6350: 6665444, 6400: 6667654, 6450: 6676787, 6500: 6678999, 6550: 6766777, 6600: 6776766, 6650: 6778899, 6700: 6788988, 6750: 7655454, 6800: 7665434, 6850: 7666788, 6900: 7676777, 6950: 7678989, 7000: 7766767, 7050: 7776678, 7100: 7778889, 7150: 7788899, 7200: 7877666, 7250: 7887676, 7300: 7889987, 7350: 8765544, 7400: 8767676, 7450: 8777665, 7500: 8787667, 7550: 8789899, 7600: 8877789, 7650: 8887877, 7700: 8898789, 7750: 8987889, 7800: 8998887, 7850: 9877654, 7900: 9887656, 7950: 9889888, 8000: 9987676, 8050: 9989987, 8100: 10000121, 8150: 10011123, 8200: 10101001, 8250: 10111221, 8300: 10121223, 8350: 10123434, 8400: 11010111, 8450: 11012343, 8500: 11110123, 8550: 11121001, 8600: 11123221, 8650: 11211210, 8700: 11221212, 8750: 11223345, 8800: 11233334, 8850: 12100121, 8900: 12111123, 8950: 12121211, 9000: 12123344, 9050: 12212112, 9100: 12222122, 9150: 12232111, 9200: 12234321, 9250: 12322101, 9300: 12323455, 9350: 12333444, 9400: 12343432, 9450: 12345556, 9500: 21010010, 9550: 21012321, 9600: 21110101, 9650: 21112333, 9700: 21122343, 9750: 21211110, 9800: 21221112, 9850: 21223323, 9900: 21233234, 9950: 22100012, 10000: 22111101, 10050: 22121111, 10100: 22123322, 10150: 22211233, 10200: 22222100, 10250: 22223454, 10300: 22233443, 10350: 22321222, 10400: 22323433, 10450: 22333344, 10500: 22343332, 10550: 22345456, 10600: 23211223, 10650: 23221233, 10700: 23223444, 10750: 23233433, 10800: 23321212, 10850: 23323345, 10900: 23333334, 10950: 23343322, 11000: 23345454, 11050: 23433221, 11100: 23434567, 11150: 23444555, 11200: 23454543, 11250: 23456667, 11300: 32110010, 11350: 32112321, 11400: 32122323, 11450: 32211011, 11500: 32221100, 11550: 32223233, 11600: 32233222, 11650: 32321000, 11700: 32323212, 11750: 32332345, 11800: 32334555, 11850: 32344543, 11900: 33211001, 11950: 33221011, 12000: 33223223, 12050: 33233212, 12100: 33234566, 12150: 33323210, 12200: 33332343, 12250: 33334545, 12300: 33344455, 12350: 33432222, 12400: 33434432, 12450: 33444334, 12500: 33454322, 12550: 33455676, 12600: 34321233, 12650: 34323444, 12700: 34333433, 12750: 34343343, 12800: 34345545, 12850: 34433234, 12900: 34443222, 12950: 34445432, 13000: 34454556, 13050: 34456766, 13100: 34544454, 13150: 34554434, 13200: 34556566, 13250: 34566554, 13300: 43210000, 13350: 43212233, 13400: 43222321, 13450: 43232232, 13500: 43234434, 13550: 43322222, 13600: 43332211, 13650: 43334343, 13700: 43344323, 13750: 43345677, 13800: 43433444, 13850: 43443432, 13900: 43445556, 13950: 43455544, 14000: 44321101, 14050: 44323234, 14100: 44333223, 14150: 44343211, 14200: 44344565, 14250: 44432332, 14300: 44434456, 14350: 44444444, 14400: 44454432, 14450: 44456556, 14500: 44544322, 14550: 44545676, 14600: 44555656, 14650: 44565566, 14700: 44567776, 14750: 45433322, 14800: 45443232, 14850: 45445434, 14900: 45454566, 14950: 45456776, 15000: 45544456, 15050: 45554444, 15100: 45556654, 15150: 45566556, 15200: 45654323, 15250: 45655677, 15300: 45665665, 15350: 45667789, 15400: 45677778, 15450: 54321221, 15500: 54323432, 15550: 54333343, 15600: 54343323, 15650: 54345455, 15700: 54433222, 15750: 54443210, 15800: 54444556, 15850: 54454544, 15900: 54456676, 15950: 54544434, 16000: 54554344, 16050: 54556554, 16100: 54565678, 16150: 54567888, 16200: 55433434, 16250: 55443344, 16300: 55445554, 16350: 55455456, 16400: 55543222, 16450: 55545432, 16500: 55554556, 16550: 55556766, 16600: 55566676, 16650: 55654443, 16700: 55656567, 16750: 55666555, 16800: 55676544, 16850: 55677898, 16900: 56543456, 16950: 56545666, 17000: 56555654, 17050: 56565556, 17100: 56567766, 17150: 56655455, 17200: 56665443, 17250: 56666789, 17300: 56676778, 17350: 56678998, 17400: 56766776, 17450: 56776765, 17500: 56778898, 17550: 56788987, 17600: 65433232, 17650: 65443212, 17700: 65444566, 17750: 65454554, 17800: 65456678, 17850: 65544444, 17900: 65554432, 17950: 65556556, 18000: 65566544, 18050: 65567898, 18100: 65655665, 18150: 65665567, 18200: 65667777, 18250: 65677766, 18300: 66543332, 18350: 66545456, 18400: 66555444, 18450: 66565432, 18500: 66566778, 18550: 66654545, 18600: 66656677, 18650: 66666665, 18700: 66676654, 18750: 66678787, 18800: 66766566, 18850: 66776555, 18900: 66778766, 18950: 66788776, 19000: 67654543, 19050: 67656667, 19100: 67666655, 19150: 67676566, 19200: 67678777, 19250: 67766556, 19300: 67776545, 19350: 67777899, 19400: 67788766, 19450: 67876677, 19500: 67878888, 19550: 67888898, 19600: 67899987, 19650: 76544543, 19700: 76554445, 19750: 76556655, 19800: 76566565, 19850: 76654332, 19900: 76655678, 19950: 76665666, 20000: 76667876, 20050: 76677787, 20100: 76765567, 20150: 76767777, 20200: 76777766, 20250: 76787776, 20300: 77654322, 20350: 77655676, 20400: 77665656, 20450: 77667788, 20500: 77677777, 20550: 77765565, 20600: 77767767, 20650: 77777678, 20700: 77787766, 20750: 77789999, 20800: 77877888, 20850: 77887898, 20900: 77898888, 20950: 78766544, 21000: 78767898, 21050: 78777887, 21100: 78787889, 21150: 78876665, 21200: 78878876, 21250: 78888878, 21300: 78899888, 21350: 78988898, 21400: 78999987, 21450: 87655654, 21500: 87665556, 21550: 87667766, 21600: 87677677, 21650: 87765543, 21700: 87767667, 21750: 87777656, 21800: 87787666, 21850: 87789898, 21900: 87877788, 21950: 87887876, 22000: 87898788, 22050: 88765666, 22100: 88767876, 22150: 88777787, 22200: 88787789, 22250: 88876565, 22300: 88878776, 22350: 88888778, 22400: 88898998, 22450: 88988876, 22500: 88999878, 22550: 89877776, 22600: 89887778, 22650: 89898776, 22700: 89987876, 22750: 89998788, 22800: 98765666, 22850: 98767876, 22900: 98777787, 22950: 98787789, 23000: 98876565, 23050: 98878776, 23100: 98888778, 23150: 98898998, 23200: 98988876, 23250: 98999878, 23300: 99877776, 23350: 99887778, 23400: 99898776, 23450: 99987876, 23500: 99998788, 23550: 100001112, 23600: 100012110, 23650: 100101210, 23700: 100112122, 23750: 100122210, 23800: 101000100, 23850: 101011110, 23900: 101100112, 23950: 101111122, 24000: 101121210, 24050: 101123343, 24100: 101212111, 24150: 101222121, 24200: 101232110, 24250: 101233456, 24300: 110001112, 24350: 110012110, 24400: 110101210, 24450: 110112122, 24500: 110122210, 24550: 111000100, 24600: 111011110, 24650: 111100112, 24700: 111111122, 24750: 111121210, 24800: 111123343, 24850: 111212111, 24900: 111222121, 24950: 111232110, 25000: 111233456, 25050: 112101112, 25100: 112112110, 25150: 112122112, 25200: 112210001, 25250: 112212234, 25300: 112222322, 25350: 112232233, 25400: 112234443, 25450: 112322223, 25500: 112332212, 25550: 112334344, 25600: 112344332, 25650: 112345678, 25700: 121011001, 25750: 121100011, 25800: 121111100, 25850: 121121110, 25900: 121123321, 25950: 121211232, 26000: 121221234, 26050: 121223445, 26100: 121233434, 26150: 122101011, 26200: 122111223, 26250: 122121233, 26300: 122123444, 26350: 122212212, 26400: 122222222, 26450: 122232211, 26500: 122234343, 26550: 122322123, 26600: 122332112, 26650: 122334322, 26700: 122343454, 26750: 122345656, 26800: 123212210, 26850: 123222212, 26900: 123232123, 26950: 123234333, 27000: 123322121, 27050: 123332110, 27100: 123333456, 27150: 123343444, 27200: 123345654, 27250: 123433343, 27300: 123443323, 27350: 123445455, 27400: 123455443, 27450: 123456789, 27500: 210011001, 27550: 210100011, 27600: 210111100, 27650: 210121110, 27700: 210123321, 27750: 211001232, 27800: 211012222, 27850: 211110001, 27900: 211112234, 27950: 211122322, 28000: 211211010, 28050: 211221012, 28100: 211223232, 28150: 211233221, 28200: 211234567, 28250: 212111001, 28300: 212121011, 28350: 212123223, 28400: 212211212, 28450: 212221222, 28500: 212223433, 28550: 212233344, 28600: 212321123, 28650: 212323334, 28700: 212333323, 28750: 212343233, 28800: 212345443, 28850: 221001210, 28900: 221012122, 28950: 221101222, 29000: 221112212, 29050: 221122222, 29100: 221210112, 29150: 221212344, 29200: 221223210, 29250: 221232343, 29300: 221234545, 29350: 222110111, 29400: 222112343, 29450: 222122345, 29500: 222211112, 29550: 222221122, 29600: 222223333, 29650: 222233322, 29700: 222321101, 29750: 222323234, 29800: 222333223, 29850: 222343211, 29900: 222344565, 29950: 223211110, 30000: 223221112, 30050: 223223323, 30100: 223233234, 30150: 223321012, 30200: 223323232, 30250: 223333221, 30300: 223334567, 30350: 223344555, 30400: 223432322, 30450: 223434454, 30500: 223444434, 30550: 223454344, 30600: 223456554, 30650: 232101210, 30700: 232112122, 30750: 232122210, 30800: 232210100, 30850: 232212332, 30900: 232222334, 30950: 232232323, 31000: 232234455, 31050: 232322321, 31100: 232332232, 31150: 232334434, 31200: 232344344, 31250: 233210011, 31300: 233212322, 31350: 233222332, 31400: 233232321, 31450: 233234445, 31500: 233322233, 31550: 233332222, 31600: 233334432, 31650: 233344334, 31700: 233432101, 31750: 233433455, 31800: 233443443, 31850: 233445567, 31900: 233455555, 31950: 234321112, 32000: 234323323, 32050: 234333234, 32100: 234343222, 32150: 234345432, 32200: 234432343, 32250: 234434545, 32300: 234444455, 32350: 234454443, 32400: 234456567, 32450: 234544333, 32500: 234554321, 32550: 234555667, 32600: 234565655, 32650: 234567787, 32700: 321010012, 32750: 321012323, 32800: 321110111, 32850: 321112343, 32900: 321122345, 32950: 321211112, 33000: 321221122, 33050: 321223333, 33100: 321233322, 33150: 322100101, 33200: 322111111, 33250: 322121121, 33300: 322123332, 33350: 322212100, 33400: 322222110, 33450: 322223456, 33500: 322233445, 33550: 322321232, 33600: 322323443, 33650: 322333432, 33700: 322343334, 33750: 322345544, 33800: 323211233, 33850: 323222100, 33900: 323223454, 33950: 323233443, 34000: 323321222, 34050: 323323433, 34100: 323333344, 34150: 323343332, 34200: 323345456, 34250: 323433223, 34300: 323443211, 34350: 323444565, 34400: 323454545, 34450: 323456677, 34500: 332110012, 34550: 332112323, 34600: 332122333, 34650: 332211100, 34700: 332221110, 34750: 332223321, 34800: 332233232, 34850: 332321010, 34900: 332323222, 34950: 332333211, 35000: 332334565, 35050: 332344545, 35100: 333211011, 35150: 333221100, 35200: 333223233, 35250: 333233222, 35300: 333321000, 35350: 333323212, 35400: 333332345, 35450: 333334555, 35500: 333344543, 35550: 333432232, 35600: 333434434, 35650: 333444344, 35700: 333454332, 35750: 333455678, 35800: 334322100, 35850: 334323454, 35900: 334333443, 35950: 334343345, 36000: 334345555, 36050: 334433322, 36100: 334443232, 36150: 334445434, 36200: 334454566, 36250: 334456776, 36300: 334544456, 36350: 334554444, 36400: 334556654, 36450: 334566556, 36500: 343210010, 36550: 343212321, 36600: 343222323, 36650: 343232234, 36700: 343234444, 36750: 343322232, 36800: 343332221, 36850: 343334345, 36900: 343344333, 36950: 343432100, 37000: 343433454, 37050: 343443434, 37100: 343445566, 37150: 343455554, 37200: 344321111, 37250: 344323322, 37300: 344333233, 37350: 344343221, 37400: 344344567, 37450: 344432334, 37500: 344434544, 37550: 344444454, 37600: 344454434, 37650: 344456566, 37700: 344544332, 37750: 344545678, 37800: 344555666, 37850: 344565654, 37900: 344567778, 37950: 345433332, 38000: 345443234, 38050: 345445444, 38100: 345455432, 38150: 345456778, 38200: 345544544, 38250: 345554454, 38300: 345556656, 38350: 345566566, 38400: 345654333, 38450: 345656543, 38500: 345665667, 38550: 345667877, 38600: 345677788, 38650: 432101100, 38700: 432111233, 38750: 432122100, 38800: 432123454, 38850: 432212222, 38900: 432222232, 38950: 432232221, 39000: 432234345, 39050: 432322211, 39100: 432332122, 39150: 432334332, 39200: 432343456, 39250: 432345666, 39300: 433212212, 39350: 433222222, 39400: 433232211, 39450: 433234343, 39500: 433322123, 39550: 433332112, 39600: 433334322, 39650: 433343454, 39700: 433345656, 39750: 433433345, 39800: 433443333, 39850: 433445543, 39900: 433455445, 39950: 434321001, 40000: 434323221, 40050: 434333210, 40100: 434334556, 40150: 434344544, 40200: 434432233, 40250: 434434443, 40300: 434444345, 40350: 434454333, 40400: 434456543, 40450: 434543445, 40500: 434545655, 40550: 434555565, 40600: 434565545, 40650: 434567677, 40700: 443211223, 40750: 443221233, 40800: 443223444, 40850: 443233433, 40900: 443321212, 40950: 443323345, 41000: 443333334, 41050: 443343322, 41100: 443345454, 41150: 443433221, 41200: 443434567, 41250: 443444555, 41300: 443454543, 41350: 443456667, 41400: 444322233, 41450: 444332222, 41500: 444334432, 41550: 444344334, 41600: 444432101, 41650: 444433455, 41700: 444443443, 41750: 444445567, 41800: 444455555, 41850: 444543321, 41900: 444545445, 41950: 444555433, 42000: 444556787, 42050: 444566767, 42100: 445432321, 42150: 445434445, 42200: 445444433, 42250: 445454343, 42300: 445456545, 42350: 445543455, 42400: 445545665, 42450: 445555567, 42500: 445565555, 42550: 445567765, 42600: 445655454, 42650: 445665434, 42700: 445666788, 42750: 445676777, 42800: 445678989, 42850: 454322345, 42900: 454332334, 42950: 454334544, 43000: 454344454, 43050: 454432221, 43100: 454434345, 43150: 454444333, 43200: 454454321, 43250: 454455667, 43300: 454543433, 43350: 454545565, 43400: 454555545, 43450: 454565455, 43500: 454567665, 43550: 455433211, 43600: 455434565, 43650: 455444545, 43700: 455454455, 43750: 455456665, 43800: 455544345, 43850: 455554333, 43900: 455556543, 43950: 455565667, 44000: 455567877, 44050: 455655566, 44100: 455665554, 44150: 455667678, 44200: 455677667, 44250: 456543233, 44300: 456545443, 44350: 456554567, 44400: 456556777, 44450: 456566765, 44500: 456654454, 44550: 456656656, 44600: 456666566, 44650: 456676555, 44700: 456678766, 44750: 456766545, 44800: 456767899, 44850: 456777888, 44900: 456787898, 44950: 543211000, 45000: 543221010, 45050: 543223222, 45100: 543233211, 45150: 543234565, 45200: 543322345, 45250: 543332334, 45300: 543334544, 45350: 543344454, 45400: 543432221, 45450: 543434345, 45500: 543444333, 45550: 543454321, 45600: 543455667, 45650: 544321232, 45700: 544323443, 45750: 544333432, 45800: 544343334, 45850: 544345544, 45900: 544433233, 45950: 544443221, 46000: 544444567, 46050: 544454555, 46100: 544456765, 46150: 544544445, 46200: 544554433, 46250: 544556565, 46300: 544566545, 46350: 544567899, 46400: 545433445, 46450: 545443433, 46500: 545445565, 46550: 545455545, 46600: 545543233, 46650: 545545443, 46700: 545554567, 46750: 545556777, 46800: 545566765, 46850: 545654454, 46900: 545656656, 46950: 545666566, 47000: 545676555, 47050: 545678766, 47100: 554322123, 47150: 554332112, 47200: 554334322, 47250: 554343454, 47300: 554345656, 47350: 554433345, 47400: 554443333, 47450: 554445543, 47500: 554455445, 47550: 554543211, 47600: 554544565, 47650: 554554545, 47700: 554556677, 47750: 554566665, 47800: 555432211, 47850: 555434343, 47900: 555444323, 47950: 555445677, 48000: 555455665, 48050: 555543345, 48100: 555545555, 48150: 555555543, 48200: 555565445, 48250: 555567655, 48300: 555654566, 48350: 555656776, 48400: 555666678, 48450: 555676667, 48500: 555678878, 48550: 556544443, 48600: 556554345, 48650: 556556555, 48700: 556566543, 48750: 556567889, 48800: 556655656, 48850: 556665566, 48900: 556667776, 48950: 556677765, 49000: 556765545, 49050: 556767677, 49100: 556777666, 49150: 556787676, 49200: 556789987, 49250: 565433433, 49300: 565443343, 49350: 565445545, 49400: 565455455, 49450: 565543221, 49500: 565544567, 49550: 565554555, 49600: 565556765, 49650: 565566667, 49700: 565654434, 49750: 565656566, 49800: 565666554, 49850: 565676543, 49900: 565677889, 49950: 566543455, 50000: 566545665, 50050: 566555567, 50100: 566565555, 50150: 566567765, 50200: 566655454, 50250: 566665434, 50300: 566666788, 50350: 566676777, 50400: 566678989, 50450: 566766767, 50500: 566776678, 50550: 566778889, 50600: 566788899, 50650: 567655444, 50700: 567665432, 50750: 567666778, 50800: 567676767, 50850: 567678987, 50900: 567766765, 50950: 567776676, 51000: 567778887, 51050: 567788889, 51100: 567877656, 51150: 567887666, 51200: 567889898, 51250: 654321111, 51300: 654323322, 51350: 654333233, 51400: 654343221, 51450: 654344567, 51500: 654432334, 51550: 654434544, 51600: 654444454, 51650: 654454434, 51700: 654456566, 51750: 654544332, 51800: 654545678, 51850: 654555666, 51900: 654565654, 51950: 654567778, 52000: 655433332, 52050: 655443234, 52100: 655445444, 52150: 655455432, 52200: 655456778, 52250: 655544544, 52300: 655554454, 52350: 655556656, 52400: 655566566, 52450: 655654333, 52500: 655656543, 52550: 655665667, 52600: 655667877, 52650: 655677788, 52700: 656543432, 52750: 656545556, 52800: 656555544, 52850: 656565454, 52900: 656567656, 52950: 656654567, 53000: 656656777, 53050: 656666765, 53100: 656676676, 53150: 656678887, 53200: 656766666, 53250: 656776655, 53300: 656778788, 53350: 656788876, 53400: 665432344, 53450: 665434554, 53500: 665444456, 53550: 665454444, 53600: 665456654, 53650: 665544334, 53700: 665554322, 53750: 665555676, 53800: 665565656, 53850: 665567788, 53900: 665655555, 53950: 665665543, 54000: 665667667, 54050: 665677656, 54100: 666543222, 54150: 666545432, 54200: 666554556, 54250: 666556766, 54300: 666566676, 54350: 666654443, 54400: 666656567, 54450: 666666555, 54500: 666676544, 54550: 666677898, 54600: 666765678, 54650: 666767888, 54700: 666777877, 54750: 666787887, 54800: 667654433, 54850: 667656565, 54900: 667666545, 54950: 667667899, 55000: 667677888, 55050: 667765676, 55100: 667767878, 55150: 667777789, 55200: 667787877, 55250: 667876567, 55300: 667878778, 55350: 667888788, 55400: 667899876, 55450: 676544433, 55500: 676554343, 55550: 676556545, 55600: 676565677, 55650: 676567887, 55700: 676655654, 55750: 676665556, 55800: 676667766, 55850: 676677677, 55900: 676765543, 55950: 676767667, 56000: 676777656, 56050: 676787666, 56100: 676789898, 56150: 677655566, 56200: 677665554, 56250: 677667678, 56300: 677677667, 56350: 677765455, 56400: 677767665, 56450: 677777654, 56500: 677787656, 56550: 677789888, 56600: 677877778, 56650: 677887788, 56700: 677898778, 56750: 678765656, 56800: 678767788, 56850: 678777777, 56900: 678787787, 56950: 678876555, 57000: 678878766, 57050: 678888776, 57100: 678898988, 57150: 678988788, 57200: 678999876, 57250: 765433323, 57300: 765443233, 57350: 765445443, 57400: 765454567, 57450: 765456777, 57500: 765544543, 57550: 765554445, 57600: 765556655, 57650: 765566565, 57700: 765654332, 57750: 765655678, 57800: 765665666, 57850: 765667876, 57900: 765677787, 57950: 766543345, 58000: 766545555, 58050: 766555543, 58100: 766565445, 58150: 766567655, 58200: 766654566, 58250: 766656776, 58300: 766666678, 58350: 766676667, 58400: 766678878, 58450: 766766665, 58500: 766776654, 58550: 766778787, 58600: 766788789, 58650: 767654556, 58700: 767656766, 58750: 767666676, 58800: 767676665, 58850: 767678876, 58900: 767766655, 58950: 767776566, 59000: 767778777, 59050: 767788787, 59100: 767876776, 59150: 767878988, 59200: 767888998, 59250: 776543210, 59300: 776544556, 59350: 776554544, 59400: 776556676, 59450: 776566656, 59500: 776654345, 59550: 776656555, 59600: 776666543, 59650: 776667889, 59700: 776677878, 59750: 776765666, 59800: 776767876, 59850: 776777787, 59900: 776787789, 59950: 777654343, 60000: 777656545, 60050: 777665677, 60100: 777667887, 60150: 777677876, 60200: 777765656, 60250: 777767788, 60300: 777777777, 60350: 777787787, 60400: 777876555, 60450: 777878766, 60500: 777888776, 60550: 777898988, 60600: 778766565, 60650: 778776554, 60700: 778778765, 60750: 778788767, 60800: 778876678, 60850: 778878889, 60900: 778888899, 60950: 778899988, 61000: 778988998, 61050: 787654321, 61100: 787655667, 61150: 787665655, 61200: 787667787, 61250: 787677776, 61300: 787765556, 61350: 787767766, 61400: 787777677, 61450: 787787765, 61500: 787789998, 61550: 787877887, 61600: 787887889, 61650: 787898887, 61700: 788766543, 61750: 788767889, 61800: 788777878, 61850: 788787888, 61900: 788876656, 61950: 788878789, 62000: 788888877, 62050: 788899887, 62100: 788988889, 62150: 788999899, 62200: 789877789, 62250: 789887877, 62300: 789898789, 62350: 789987889, 62400: 789998887, 62450: 876544321, 62500: 876545667, 62550: 876555655, 62600: 876565565, 62650: 876567767, 62700: 876655456, 62750: 876665444, 62800: 876667654, 62850: 876676787, 62900: 876678999, 62950: 876766777, 63000: 876776766, 63050: 876778899, 63100: 876788988, 63150: 877655454, 63200: 877665434, 63250: 877666788, 63300: 877676777, 63350: 877678989, 63400: 877766767, 63450: 877776678, 63500: 877778889, 63550: 877788899, 63600: 877877666, 63650: 877887676, 63700: 877889987, 63750: 878765544, 63800: 878767676, 63850: 878777665, 63900: 878787667, 63950: 878789899, 64000: 878877789, 64050: 878887877, 64100: 878898789, 64150: 878987889, 64200: 878998887, 64250: 887655432, 64300: 887656778, 64350: 887666766, 64400: 887676677, 64450: 887678888, 64500: 887766667, 64550: 887776656, 64600: 887778789, 64650: 887788877, 64700: 887876788, 64750: 887887654, 64800: 887889878, 64850: 888765444, 64900: 888767654, 64950: 888776787, 65000: 888778999, 65050: 888789877, 65100: 888877767, 65150: 888887777, 65200: 888898767, 65250: 888987789, 65300: 888998787, 65350: 889876776, 65400: 889878988, 65450: 889888998, 65500: 889987654, 65550: 889989878, 65600: 898765444, 65650: 898767654, 65700: 898776787, 65750: 898778999, 65800: 898789877, 65850: 898877767, 65900: 898887777, 65950: 898898767, 66000: 898987789, 66050: 898998787, 66100: 899876776, 66150: 899878988, 66200: 899888998, 66250: 899987654, 66300: 899989878, 66350: 987654333, 66400: 987656543, 66450: 987665667, 66500: 987667877, 66550: 987677788, 66600: 987765654, 66650: 987767778, 66700: 987777767, 66750: 987787777, 66800: 987876545, 66850: 987877899, 66900: 987888766, 66950: 987898899, 67000: 988766555, 67050: 988776544, 67100: 988777898, 67150: 988788765, 67200: 988876676, 67250: 988878887, 67300: 988888889, 67350: 988899899, 67400: 988988988, 67450: 988999998, 67500: 989877887, 67550: 989887889, 67600: 989898887, 67650: 989988766, 67700: 989998899, 67750: 998766555, 67800: 998776544, 67850: 998777898, 67900: 998788765, 67950: 998876676, 68000: 998878887, 68050: 998888889, 68100: 998899899, 68150: 998988988, 68200: 998999998, 68250: 999877887, 68300: 999887889, 68350: 999898887, 68400: 999988766, 68450: 999998899, 68500: 1000001223, 68550: 1000012221, 68600: 1000110000, 68650: 1000112233, 68700: 1000122321, 68750: 1001001001, 68800: 1001011221, 68850: 1001101100, 68900: 1001111233, 68950: 1001122100, 69000: 1001123454, 69050: 1001212222, 69100: 1001222232, 69150: 1001232221, 69200: 1001234345, 69250: 1010001223, 69300: 1010012221, 69350: 1010110000, 69400: 1010112233, 69450: 1010122321, 69500: 1011001001, 69550: 1011011221, 69600: 1011101100, 69650: 1011111233, 69700: 1011122100, 69750: 1011123454, 69800: 1011212222, 69850: 1011222232, 69900: 1011232221, 69950: 1011234345, 70000: 1012101223, 70050: 1012112221, 70100: 1012122223, 70150: 1012210121, 70200: 1012212345, 70250: 1012223211, 70300: 1012232344, 70350: 1012234554, 70400: 1012322334, 70450: 1012332323, 70500: 1012334455, 70550: 1012344443, 70600: 1100000111, 70650: 1100011121, 70700: 1100100123, 70750: 1100111211, 70800: 1100121221, 70850: 1100123432, 70900: 1101010101, 70950: 1101012333, 71000: 1101110121, 71050: 1101112345, 71100: 1101123211, 71150: 1101211122, 71200: 1101221210, 71250: 1101223343, 71300: 1101233332, 71350: 1110000111, 71400: 1110011121, 71450: 1110100123, 71500: 1110111211, 71550: 1110121221, 71600: 1110123432, 71650: 1111010101, 71700: 1111012333, 71750: 1111110121, 71800: 1111112345, 71850: 1111123211, 71900: 1111211122, 71950: 1111221210, 72000: 1111223343, 72050: 1111233332, 72100: 1112100111, 72150: 1112111121, 72200: 1112121123, 72250: 1112123334, 72300: 1112212110, 72350: 1112222112, 72400: 1112232101, 72450: 1112233455, 72500: 1112321234, 72550: 1112323445, 72600: 1112333434, 72650: 1112343344, 72700: 1112345554, 72750: 1121010000, 72800: 1121012233, 72850: 1121110012, 72900: 1121112323, 72950: 1121122333, 73000: 1121211100, 73050: 1121221110, 73100: 1121223321, 73150: 1121233232, 73200: 1122100010, 73250: 1122111012, 73300: 1122121101, 73350: 1122123234, 73400: 1122211223, 73450: 1122221233, 73500: 1122223444, 73550: 1122233433, 73600: 1122321212, 73650: 1122323345, 73700: 1122333334, 73750: 1122343322, 73800: 1122345454, 73850: 1123211221, 73900: 1123221223, 73950: 1123223434, 74000: 1123233345, 74050: 1123321210, 74100: 1123323343, 74150: 1123333332, 74200: 1123343234, 74250: 1123345444, 74300: 1123433211, 74350: 1123434565, 74400: 1123444545, 74450: 1123454455, 74500: 1123456665, 74550: 1210010000, 74600: 1210012233, 74650: 1210110012, 74700: 1210112323, 74750: 1210122333, 74800: 1211001100, 74850: 1211011233, 74900: 1211101112, 74950: 1211112110, 75000: 1211122112, 75050: 1211210001, 75100: 1211212234, 75150: 1211222322, 75200: 1211232233, 75250: 1211234443, 75300: 1212110000, 75350: 1212112233, 75400: 1212122321, 75450: 1212211001, 75500: 1212221011, 75550: 1212223223, 75600: 1212233212, 75650: 1212234566, 75700: 1212323210, 75750: 1212332343, 75800: 1212334545, 75850: 1212344455, 75900: 1221000123, 75950: 1221011211, 76000: 1221101011, 76050: 1221111223, 76100: 1221121233, 76150: 1221123444, 76200: 1221212212, 76250: 1221222222, 76300: 1221232211, 76350: 1221234343, 76400: 1222101221, 76450: 1222112211, 76500: 1222122221, 76550: 1222210111, 76600: 1222212343, 76650: 1222222345, 76700: 1222232334, 76750: 1222234544, 76800: 1222322332, 76850: 1222332321, 76900: 1222334445, 76950: 1222344433, 77000: 1223210101, 77050: 1223212333, 77100: 1223222343, 77150: 1223232332, 77200: 1223234456, 77250: 1223322322, 77300: 1223332233, 77350: 1223334443, 77400: 1223344345, 77450: 1223432112, 77500: 1223434322, 77550: 1223443454, 77600: 1223445656, 77650: 1223455566, 77700: 1232100123, 77750: 1232111211, 77800: 1232121221, 77850: 1232123432, 77900: 1232212122, 77950: 1232222210, 78000: 1232232121, 78050: 1232234323, 78100: 1232322111, 78150: 1232332100, 78200: 1232333454, 78250: 1232343434, 78300: 1232345566, 78350: 1233212112, 78400: 1233222122, 78450: 1233232111, 78500: 1233234321, 78550: 1233322101, 78600: 1233323455, 78650: 1233333444, 78700: 1233343432, 78750: 1233345556, 78800: 1233433323, 78850: 1233443233, 78900: 1233445443, 78950: 1233454567, 79000: 1233456777, 79050: 1234322343, 79100: 1234332332, 79150: 1234334456, 79200: 1234344444, 79250: 1234432211, 79300: 1234434343, 79350: 1234444323, 79400: 1234445677, 79450: 1234455665, 79500: 1234543345, 79550: 1234545555, 79600: 1234555543, 79650: 1234565445, 79700: 1234567655, 79750: 2100001123, 79800: 2100012121, 79850: 2100101221, 79900: 2100112211, 79950: 2100122221, 80000: 2101000111, 80050: 2101011121, 80100: 2101100123, 80150: 2101111211, 80200: 2101121221, 80250: 2101123432, 80300: 2101212122, 80350: 2101222210, 80400: 2101232121, 80450: 2101234323, 80500: 2110001123, 80550: 2110012121, 80600: 2110101221, 80650: 2110112211, 80700: 2110122221, 80750: 2111000111, 80800: 2111011121, 80850: 2111100123, 80900: 2111111211, 80950: 2111121221, 81000: 2111123432, 81050: 2111212122, 81100: 2111222210, 81150: 2111232121, 81200: 2111234323, 81250: 2112101123, 81300: 2112112121, 81350: 2112122123, 81400: 2112210012, 81450: 2112212323, 81500: 2112222333, 81550: 2112232322, 81600: 2112234454, 81650: 2112322234, 81700: 2112332223, 81750: 2112334433, 81800: 2112344343, 81850: 2121000010, 81900: 2121011012, 81950: 2121100101, 82000: 2121111111, 82050: 2121121121, 82100: 2121123332, 82150: 2121212100, 82200: 2121222110, 82250: 2121223456, 82300: 2121233445, 82350: 2122101101, 82400: 2122111234, 82450: 2122122101, 82500: 2122123455, 82550: 2122212223, 82600: 2122222233, 82650: 2122232222, 82700: 2122234432, 82750: 2122322212, 82800: 2122332123, 82850: 2122334333, 82900: 2122344321, 82950: 2122345667, 83000: 2123212221, 83050: 2123222223, 83100: 2123232212, 83150: 2123234344, 83200: 2123322210, 83250: 2123332121, 83300: 2123334323, 83350: 2123343455, 83400: 2123345665, 83450: 2123433432, 83500: 2123443334, 83550: 2123445544, 83600: 2123455454, 83650: 2210000010, 83700: 2210011012, 83750: 2210100101, 83800: 2210111111, 83850: 2210121121, 83900: 2210123332, 83950: 2211010000, 84000: 2211012233, 84050: 2211110012, 84100: 2211112323, 84150: 2211122333, 84200: 2211211100, 84250: 2211221110, 84300: 2211223321, 84350: 2211233232, 84400: 2212100010, 84450: 2212111012, 84500: 2212121101, 84550: 2212123234, 84600: 2212211223, 84650: 2212221233, 84700: 2212223444, 84750: 2212233433, 84800: 2212321212, 84850: 2212323345, 84900: 2212333334, 84950: 2212343322, 85000: 2212345454, 85050: 2221001221, 85100: 2221012211, 85150: 2221101233, 85200: 2221112223, 85250: 2221122233, 85300: 2221210123, 85350: 2221221001, 85400: 2221223221, 85450: 2221233210, 85500: 2221234556, 85550: 2222110122, 85600: 2222121000, 85650: 2222123212, 85700: 2222211123, 85750: 2222221211, 85800: 2222223344, 85850: 2222233333, 85900: 2222321112, 85950: 2222323323, 86000: 2222333234, 86050: 2222343222, 86100: 2222345432, 86150: 2223211121, 86200: 2223221123, 86250: 2223223334, 86300: 2223233323, 86350: 2223321110, 86400: 2223323321, 86450: 2223333232, 86500: 2223343212, 86550: 2223344566, 86600: 2223432333, 86650: 2223434543, 86700: 2223444445, 86750: 2223454433, 86800: 2223456565, 86850: 2232101221, 86900: 2232112211, 86950: 2232122221, 87000: 2232210111, 87050: 2232212343, 87100: 2232222345, 87150: 2232232334, 87200: 2232234544, 87250: 2232322332, 87300: 2232332321, 87350: 2232334445, 87400: 2232344433, 87450: 2233210101, 87500: 2233212333, 87550: 2233222343, 87600: 2233232332, 87650: 2233234456, 87700: 2233322322, 87750: 2233332233, 87800: 2233334443, 87850: 2233344345, 87900: 2233432112, 87950: 2233434322, 88000: 2233443454, 88050: 2233445656, 88100: 2233455566, 88150: 2234321123, 88200: 2234323334, 88250: 2234333323, 88300: 2234343233, 88350: 2234345443, 88400: 2234433210, 88450: 2234434556, 88500: 2234444544, 88550: 2234454454, 88600: 2234456656, 88650: 2234544344, 88700: 2234554332, 88750: 2234555678, 88800: 2234565666, 88850: 2234567876, 88900: 2321010110, 88950: 2321012334, 89000: 2321110122, 89050: 2321121000, 89100: 2321123212, 89150: 2321211123, 89200: 2321221211, 89250: 2321223344, 89300: 2321233333, 89350: 2322100112, 89400: 2322111122, 89450: 2322121210, 89500: 2322123343, 89550: 2322212111, 89600: 2322222121, 89650: 2322232110, 89700: 2322233456, 89750: 2322322100, 89800: 2322323454, 89850: 2322333443, 89900: 2322343345, 89950: 2322345555, 90000: 2323212101, 90050: 2323222111, 90100: 2323232100, 90150: 2323233454, 90200: 2323321233, 90250: 2323323444, 90300: 2323333433, 90350: 2323343343, 90400: 2323345545, 90450: 2323433234, 90500: 2323443222, 90550: 2323445432, 90600: 2323454556, 90650: 2323456766, 90700: 2332110110, 90750: 2332112334, 90800: 2332122344, 90850: 2332211111, 90900: 2332221121, 90950: 2332223332, 91000: 2332233321, 91050: 2332321100, 91100: 2332323233, 91150: 2332333222, 91200: 2332343210, 91250: 2332344556, 91300: 2333211101, 91350: 2333221111, 91400: 2333223322, 91450: 2333233233, 91500: 2333321011, 91550: 2333323223, 91600: 2333333212, 91650: 2333334566, 91700: 2333344554, 91750: 2333432321, 91800: 2333434445, 91850: 2333444433, 91900: 2333454343, 91950: 2333456545, 92000: 2334322111, 92050: 2334332100, 92100: 2334333454, 92150: 2334343434, 92200: 2334345566, 92250: 2334433333, 92300: 2334443321, 92350: 2334445445, 92400: 2334455433, 92450: 2334456787, 92500: 2334544545, 92550: 2334554455, 92600: 2334556665, 92650: 2334566567, 92700: 2343210100, 92750: 2343212332, 92800: 2343222334, 92850: 2343232323, 92900: 2343234455, 92950: 2343322321, 93000: 2343332232, 93050: 2343334434, 93100: 2343344344, 93150: 2343432111, 93200: 2343434321, 93250: 2343443445, 93300: 2343445655, 93350: 2343455565, 93400: 2344321122, 93450: 2344323333, 93500: 2344333322, 93550: 2344343232, 93600: 2344345434, 93650: 2344432345, 93700: 2344434555, 93750: 2344444543, 93800: 2344454445, 93850: 2344456655, 93900: 2344544343, 93950: 2344554323, 94000: 2344555677, 94050: 2344565665, 94100: 2344567789, 94150: 2345433343, 94200: 2345443323, 94250: 2345445455, 94300: 2345455443, 94350: 2345456789, 94400: 2345544555, 94450: 2345554543, 94500: 2345556667, 94550: 2345566655, 94600: 2345654344, 94650: 2345656554, 94700: 2345665678, 94750: 2345667888, 94800: 2345677877, 94850: 3210001111, 94900: 3210012101, 94950: 3210101123, 95000: 3210112121, 95050: 3210122123, 95100: 3211000012, 95150: 3211011101, 95200: 3211100111, 95250: 3211111121, 95300: 3211121123, 95350: 3211123334, 95400: 3211212110, 95450: 3211222112, 95500: 3211232101, 95550: 3211233455, 95600: 3212101111, 95650: 3212112101, 95700: 3212122111, 95750: 3212210000, 95800: 3212212233, 95850: 3212222321, 95900: 3212232232, 95950: 3212234434, 96000: 3212322222, 96050: 3212332211, 96100: 3212334343, 96150: 3212344323, 96200: 3212345677, 96250: 3221011000, 96300: 3221100010, 96350: 3221111012, 96400: 3221121101, 96450: 3221123234, 96500: 3221211223, 96550: 3221221233, 96600: 3221223444, 96650: 3221233433, 96700: 3222101010, 96750: 3222111222, 96800: 3222121232, 96850: 3222123443, 96900: 3222212211, 96950: 3222222221, 97000: 3222232210, 97050: 3222234334, 97100: 3222322122, 97150: 3222332111, 97200: 3222334321, 97250: 3222343445, 97300: 3222345655, 97350: 3223212123, 97400: 3223222211, 97450: 3223232122, 97500: 3223234332, 97550: 3223322112, 97600: 3223332101, 97650: 3223333455, 97700: 3223343443, 97750: 3223345567, 97800: 3223433334, 97850: 3223443322, 97900: 3223445454, 97950: 3223455434, 98000: 3223456788, 98050: 3232111000, 98100: 3232121010, 98150: 3232123222, 98200: 3232211211, 98250: 3232221221, 98300: 3232223432, 98350: 3232233343, 98400: 3232321122, 98450: 3232323333, 98500: 3232333322, 98550: 3232343232, 98600: 3232345434, 98650: 3233211123, 98700: 3233221211, 98750: 3233223344, 98800: 3233233333, 98850: 3233321112, 98900: 3233323323, 98950: 3233333234, 99000: 3233343222, 99050: 3233345432, 99100: 3233432343, 99150: 3233434545, 99200: 3233444455, 99250: 3233454443, 99300: 3233456567, 99350: 3234322211, 99400: 3234332122, 99450: 3234334332, 99500: 3234343456, 99550: 3234345666, 99600: 3234433433, 99650: 3234443343, 99700: 3234445545, 99750: 3234455455, 99800: 3234543221, 99850: 3234544567, 99900: 3234554555, 99950: 3234556765,100000:3234566667}


def runrun(n):
    n=str(n)
    for i in range(len(n)-1):
        if abs(int(n[i])-int(n[i+1]))>1:
            return False
    return True

K=int(input())
K+=1

sep=50

i=d[(K//sep)*sep]
count=(K//sep)*sep
while True:
    if count==K:
        break
    if runrun(i):
        count+=1
    i+=1

print(i-1)