09_input.txt

5
48
36
14
3
6
11
32
50
17
27
7
21
38
28
30
19
35
22
24
49
37
12
41
43
8
9
25
29
14
13
15
16
84
20
26
17
59
51
21
27
31
64
23
28
22
58
24
34
30
36
32
35
89
29
33
37
41
50
47
40
38
52
43
67
79
53
45
55
65
46
121
74
106
59
61
62
72
70
66
114
75
78
81
83
85
84
117
98
128
91
99
100
101
105
108
120
231
121
123
127
132
138
136
210
153
185
159
164
230
169
182
203
331
212
191
199
265
221
213
228
243
244
248
453
382
268
496
289
317
312
744
555
481
644
413
601
949
419
390
404
427
434
502
441
667
630
492
516
884
557
580
725
716
629
702
794
803
973
824
809
817
896
1586
1194
831
929
875
1464
933
1121
1490
1008
1742
1137
1345
2302
1924
1757
1331
1505
2129
1764
1626
1753
1648
1692
3234
3405
1968
1706
3153
2145
2070
2829
2513
3449
3105
2468
2482
3258
2836
2957
3725
2979
3131
3616
3274
3318
3398
4837
3660
5102
5771
4450
3776
7968
4538
5349
4950
4981
5461
5304
5726
5318
8920
5793
5936
7123
6110
8592
6592
6672
6716
10474
9375
11976
10268
8226
8314
9094
17437
9488
24029
9931
10774
10622
11030
11836
15437
11729
11903
18582
30701
12702
20553
18469
13388
14942
16540
27570
17714
19716
17802
32282
19025
22677
19419
20705
28956
21396
30504
38185
23565
30198
32434
31284
26090
27644
44118
51853
40421
28330
35565
58242
56594
37221
36827
56288
38444
39730
40124
40815
54069
69655
44961
49655
51209
51895
60078
57374
53734
64471
55974
92513
63895
92710
76557
101298
74048
92024
116287
75271
126480
78174
96856
104710
96170
99030
143919
102335
100864
193322
131908
109708
111108
117629
157272
139166
225995
151828
303030
203633
248629
149319
304169
210082
243016
201365
179038
193026
195200
197034
387795
203199
232772
210572
220816
227337
228737
343880
256795
288485
334366
301147
328357
344519
342345
352518
346353
477611
425798
372064
374238
376072
392234
398399
443344
563103
413771
431388
439309
448153
591161
744491
653665
545280
589632
629504
740744
686864
688698
830129
698871
744752
764298
857186
746302
807460
845159
984589
812170
853080
993433
861924
870697
1039314
1370248
1136441
1134912
2177708
1174784
1276496
1316368
1387569
1375562
1433450
1443623
1445173
1491054
1510600
2569891
2304147
1657329
1665250
1674094
1682867
1715004
1901238
1732621
1910011
2174226
2271353
2309696
3148383
2451280
2491152
2592864
2691930
3866714
2809012
2877073
2888796
2936227
6037179
6138067
4621417
9015140
3322579
3339344
4491879
3592878
3447625
3633859
3642632
4902560
5063022
5718978
4760976
5915443
4942432
5084016
5284794
5500942
5686085
5745239
5825023
6211375
6258806
6981976
6661923
7235510
6770204
6786969
6932222
8510647
7040503
8576291
9319944
8545192
11693198
12266770
9703408
13518723
10026448
13861085
10368810
12036398
11431324
11511108
11570262
12757245
12470181
13752180
18805772
15551150
16106913
13702426
13719191
13972725
15585695
16743911
22406277
19023352
30716636
22838991
19729856
25897483
25755589
20395258
21800134
21879918
22942432
23001586
25542987
24040443
25227426
26172607
27421617
27675151
27691916
29288121
43234249
42916518
44873816
32329606
35767263
42801535
65755509
40125114
41529990
41609774
48839915
48070409
42195392
43680052
44822350
45944018
47042029
49267869
56370049
51400033
53594224
71355203
55367067
120623072
90265801
75131141
73939380
77962655
130390915
77297253
126722270
85210042
81655104
83805166
85289826
85875444
88502402
119883398
89624070
90766368
103412078
137770271
155594484
135249328
143869469
127533604
149070521
166944930
151236633
151902035
228536639
159229206
155259908
158952357
162507295
265303875
165460270
167530548
169094992
191914480
176641812
256032950
258296916
286485961
194178446
280053890
306496541
271403073
262782932
276604125
316015451
300307154
217430975
303138668
444134673
314212265
314489114
321459652
478400441
327967565
332990818
342102082
336625540
439424744
370820258
520569643
475727891
411609421
474232336
714748089
480213907
494035100
698787823
517738129
531643240
533446426
531920089
955941798
642179830
628701379
847935540
635948766
1328149447
660958383
670069647
669616358
1368505183
707445798
782429679
1053789251
1117907721
885841757
1384364447
1122393737
974249007
1965843261
1305565124
1049381369
1049658218
1063563329
1065366515
1160621468
1264650145
1270881209
1289659762
2433745816
1296907149
1330574741
2314031514
1339686005
1377062156
2666721918
2645251129
1668271436
1935499975
1860090764
2601455950
2037812336
2355026277
2113221547
2112944698
2115024733
2099039587
4669057791
2561557294
2395941256
2641712301
2535531354
2610567214
3694712282
2627481890
3978518106
2670260746
3438725592
4151033883
3045333592
4309983737
4295753326
3603771411
3795590739
3897903100
4214064320
5083145928
4211984285
4212261134
4227969431
4494980843
4634570941
4931472610
6000282886
5006508470
6841546210
5146098568
5238049104
5672815482
5297742636
6484059184
5715594338
6840924331
8522244871
8091344065
7399362150
7693493839
7501674511
8111967420
8424245419
8426048605
11053185465
8439953716
8440230565
8722950274
9129551784
9566043551
10244557574
13737973201
12078973435
15563874605
10384147672
17553797203
11013336974
19453567539
12199653522
13409088177
15092855989
15839315866
21257894548
14901036661
15195168350
24422425151
16536212839
16850294024
16866279170
16880184281
23304016752
24761211901
19950191223
19513699456
20579380525
30759042955
34606555445
25914373635
40093079981
22583801194
23212990496
25608741699
35672236514
27100690183
28310124838
29993892650
30096205011
31437249500
31731381189
32045462374
33386506863
33402492009
33716573194
40529571748
36393883737
39463890679
42097500650
42533992417
42726689952
52016630025
60355587212
45796791690
48192542893
57654204073
55986293203
48821732195
81595034902
55410815021
67119065203
67774015517
60090097661
61533454511
63776843563
65117888052
69780390600
75814073844
83256261700
107427445046
75857774416
78491384387
81997883096
124321724854
104808025398
124050317309
142933139047
93989334583
115577182290
149400149604
104232547216
143128489413
108911829856
115500912682
116944269532
136899455803
134898278652
151671848260
125310298074
128894731615
208051027099
174588415998
154305458231
154349158803
157855657512
201168072490
303749308407
222884066198
221752294930
198221881799
202901164439
209490247265
209566516873
213144377072
291204914034
399389954289
237806561471
224412742538
361312198341
242254567606
271797734455
260208576726
484942111527
254205029689
303483147613
308654617034
328937574801
433902989803
312204816315
371000034584
401123046238
407712129064
422634624337
419056764138
407788398672
412391411704
451744814871
550909184640
725107903837
462219304009
466667310144
478617772227
496459597295
778872126459
502463144332
600735309256
514413606415
562859646723
1096107938421
813514457942
620859433349
730060621039
958621313704
903586190570
772123080822
808835175302
815500527736
820179810376
831448175842
1286847120520
1002653999511
1059319244018
1464873303520
928886614153
958678901304
1065322791055
1610320302301
998922741627
1016876750747
1077273253138
1323248781717
1135273039764
1392982514171
1429694608651
1434373891291
1675709271392
1966721215606
1580958256124
1587623608558
1592302891198
2467527303031
2407803418934
1651627986218
1760334789995
2458305305226
1927809355780
2716231295888
4303854904446
4000106310132
1957601642931
2015799492374
2134195781391
2752943390368
5884813160570
2212546292902
2458521821481
4682952511494
3015332147415
3021997499849
3026676782489
3168581864682
4386331177261
3179926499756
3239251594776
7141257816720
3411962776213
6343932820192
3579437341998
3776134282369
3943608848154
4062005137171
3973401135305
7943715158286
6591889275969
4091797424322
5031131639789
6844740814690
7301256731947
5227878440317
4671068114383
6048674282338
6183914012097
10959047305701
6190579364531
6944716147051
6348508364438
6419178094532
6818688936774
6991400118211
7188097058582
7355571624367
7523046190152
7552838477303
7719743130523
8035406272476
8065198559627
8644469249688
14006785995356
8762865538705
19024245865328
9702199754172
9898946554700
11090246208915
15111373903143
13378676423113
12232588294435
13175314130308
17421992744852
12539087728969
12767686458970
16798271811181
13237867031306
18661812093405
15223503331058
20091926206272
14878617814519
21443874982740
15618037036930
15755149402999
16679875522164
16709667809315
22023145672801
32553421214180
28257294237632
19601146308872
32645496075910
23136813586006
23629333937884
24771676023404
27417705543488
25000274753405
37767961212375
31373186439929
37539362482374
26005553490276
28116484845825
28461370362364
30102121145577
30496654851449
30633767217518
42995102660344
33389543331479
32327704846245
32435024925163
41709942562720
49037372655560
41624291981673
42737959894878
48137088339411
43230480246756
73083129002649
46766147523890
48401009961288
49771950776809
61506028177304
51005828243681
54122038336101
56107674635853
56502208341725
97731966617526
58750252063343
100888185859991
60598775997026
61130422068967
198620152477517
89891751673204
99240168236603