TEST DATA FOR `roads'

Input for test 1

4 1
1 1
3 1
2 3
4 3
1 4

Output for test 1

4.00

Input for test 2

15 3
5 1
1 1
9 17
5 2
1 9
9 5
1 14
13 11
1 11
5 14
15 9
11 17
9 9
11 1
18 4
9 15
1 2
5 4

Output for test 2

37.77

Input for test 3

50 8
83 86
20 97
37 9
84 11
9 9
77 72
55 50
61 81
61 31
85 37
11 81
56 25
26 21
49 46
51 1
96 25
62 12
65 66
3 26
1 39
89 93
19 91
17 17
59 85
42 65
1 17
81 59
70 33
49 65
59 93
61 93
30 2
28 61
61 25
99 2
23 98
51 27
93 93
71 1
21 17
46 59
75 56
71 73
53 83
99 89
37 65
39 21
59 26
31 61
46 81
31 43
4 20
37 10
3 27
47 6
36 14
14 30
23 46

Output for test 3

349.51

Input for test 4

100 20
29 226
179 81
113 248
139 51
341 173
210 333
21 29
155 55
309 69
101 189
77 62
162 24
271 123
35 269
284 21
261 133
301 119
329 187
231 217
111 100
89 301
277 321
349 41
333 83
193 301
191 345
113 48
232 220
78 161
143 99
323 113
177 30
321 36
276 120
70 303
161 323
251 271
39 187
316 270
246 89
29 313
292 343
152 281
37 2
11 47
211 207
167 155
21 63
161 191
325 71
1 71
316 208
197 9
125 85
26 162
67 9
158 26
86 61
162 344
123 29
98 253
63 337
237 47
191 47
295 85
33 1
71 124
99 57
51 299
48 91
239 315
111 74
276 131
71 326
125 35
337 183
30 304
345 237
92 132
107 149
345 271
211 131
21 7
301 126
301 183
314 82
269 155
183 21
29 211
253 72
57 47
303 121
169 119
143 186
61 281
8 65
156 61
347 216
2 155
311 316
36 61
75 28
56 35
11 16
10 79
53 35
25 13
26 88
22 98
13 34
48 67
43 4
26 44
2 70
58 98
13 81
100 37
27 34
42 74
3 39

Output for test 4

1661.14

Input for test 5

200 20
915 540
137 301
338 307
611 942
533 334
795 132
486 539
163 184
751 648
801 141
713 881
41 988
711 337
473 490
686 141
189 193
917 36
497 562
258 682
641 225
253 398
705 141
49 744
761 175
705 473
253 375
623 55
583 759
277 409
114 5
756 313
681 25
541 111
801 33
503 379
976 941
728 851
709 857
571 408
887 939
881 175
461 405
928 725
771 464
501 9
961 351
95 713
329 337
239 74
433 347
721 455
505 713
601 891
795 948
785 786
407 635
259 647
881 917
321 885
318 734
431 365
969 353
825 126
573 537
361 501
233 478
873 737
109 929
773 361
56 756
714 135
245 514
759 83
601 345
283 349
411 736
363 537
33 408
817 476
590 941
981 969
361 526
405 439
525 401
821 113
161 402
237 281
606 251
585 316
126 439
967 801
701 201
843 657
119 309
573 161
401 674
902 830
141 448
286 633
169 240
379 669
839 489
77 856
965 593
31 535
489 501
121 905
871 723
553 343
926 934
831 499
217 516
805 531
7 695
308 209
706 599
425 126
709 205
397 541
816 21
921 64
576 513
973 421
156 177
956 829
69 841
551 995
444 866
975 421
373 761
705 329
666 665
86 51
958 471
774 751
547 581
426 601
593 46
840 38
114 697
92 761
356 209
121 682
869 401
199 725
9 218
356 749
17 703
903 853
607 69
671 620
31 721
641 471
249 53
189 611
399 999
860 716
391 393
425 536
905 867
611 442
720 201
945 168
140 869
207 809
735 601
51 776
361 148
283 206
821 737
147 583
801 241
203 920
831 681
311 811
852 406
431 49
181 599
307 233
161 801
481 379
105 855
383 42
982 995
641 641
615 186
309 472
611 383
912 534
860 309
323 851
356 985
191 697
685 998
758 577
1 925
23 347
137 801
714 955
29 7
40 13
180 50
181 42
61 104
119 176
3 86
136 45
37 14
84 67
149 54
15 172
54 17
60 94
149 143
154 87
135 9
12 138
68 200
176 146
82 22

Output for test 5

7742.93

Input for test 6

250 1
7665 6773
5149 8514
4441 85
7538 531
381 4781
3029 4683
4249 3671
2845 509
2561 9897
629 791
9566 2162
3949 5101
4498 4801
1201 322
4381 7698
3496 6945
4950 2342
805 5601
4198 7158
2471 2521
2803 3601
8713 2695
1826 8006
1042 6699
8065 8157
913 9105
1006 3537
4591 4241
9531 2209
1784 3857
6689 2101
195 8611
521 7254
7291 9812
5334 5161
5809 2291
47 1510
376 8944
4701 1629
3245 9727
8305 5839
9221 8869
4769 3749
8339 2705
4617 431
2449 5528
6745 7601
1865 2062
3033 623
6759 43
2861 4525
3331 6026
4797 2451
776 2929
409 1571
5705 1475
5071 1141
6595 7969
2809 8761
4028 9945
8235 6401
2631 5006
2606 4368
2755 3243
4821 1289
3186 4773
3436 5069
4239 7194
1118 6065
9883 4799
646 5987
3601 9827
2363 8703
4376 5655
7585 4131
2640 1
1751 265
5985 1857
8429 2772
6781 8866
5177 5901
3601 8332
9298 2066
101 5808
9326 4581
3481 3681
1 499
3991 3653
1803 4501
3059 4308
2163 2481
1326 5777
3783 1876
3985 5301
9607 7713
14 6941
8223 8233
9009 3938
5917 5211
5534 2511
728 4105
8227 7922
3126 9424
17 1611
5297 4435
8836 76
9451 3896
3451 8711
9107 4273
9072 8601
9237 9605
4671 1641
9601 6689
1694 9785
4811 19
657 8581
7857 9761
9379 2449
1463 557
3303 7661
6801 3361
6391 4977
5310 5951
7937 8907
2945 9051
9859 1170
5201 3841
479 2888
9201 1894
723 8337
729 7451
2128 6510
6888 6337
721 315
3027 6912
7505 3351
3495 99
6651 961
357 4659
5776 956
8201 4133
5681 3690
9972 3433
8481 4601
5877 485
6001 8500
1718 1811
9591 7593
4841 4261
9713 1157
6665 2168
5533 3485
630 7591
119 7711
801 3800
3953 1449
2397 5426
9481 9937
4681 9938
1954 4229
6661 3973
3249 8289
7246 9571
8471 851
7738 4391
2055 4969
4705 579
1595 9898
673 8373
5471 8487
5483 7046
4401 5281
3727 7469
3410 4049
849 3761
9425 4956
9069 1993
2353 4361
5397 9461
2817 5305
7936 9541
1225 7056
4335 7185
7021 2786
5772 535
7811 9641
5628 473
951 5505
5717 2544
6041 5806
7529 9843
4485 6437
2017 4115
1165 1003
56 9191
1366 9815
9531 8326
565 5347
6484 8913
6982 6476
6911 174
1021 7786
2787 8901
4543 9299
1145 3881
1611 7883
4037 5015
4526 6399
7997 5271
6561 4045
1042 6121
6033 3585
653 3105
8929 7815
318 9034
4276 4677
1441 5755
4901 4054
4769 486
3457 309
1301 6369
4681 7221
1785 807
3686 1653
5769 2148
9697 5371
5393 329
1529 6371
8571 5757
1913 5341
353 6426
2057 369
8882 2441
6885 462
7055 2129
1931 9130
1694 9101
5383 8277
3211 1061
9576 8151
1676 4961
7833 5201
3611 7411
8921 6008
5131 3353
4619 7766
5209 2848
8008 2326
8561 964
5605 7797
153 105

Output for test 6

104189.72

Input for test 7

500 12
5396 9313
27835 14471
1711 24701
67063 24759
9087 3469
85153 27122
80885 15093
50441 49210
1631 3931
47898 10105
44671 16733
75689 733
43521 61831
12553 8656
16044 46993
79696 37377
94545 30485
26551 51390
6561 71918
92177 14313
32201 26994
55829 38405
67516 14111
49542 86681
31581 34591
37401 44769
16626 50883
13411 53389
70569 55524
59391 56025
16645 10277
96290 34453
28061 41248
23333 21409
15327 21949
35262 46381
4951 12601
7758 16635
30563 12865
59029 96753
643 3541
14686 92005
45025 14796
44864 8777
12321 85333
5474 70251
52169 57601
341 77043
64601 25121
85256 52668
67402 32255
84101 37589
53776 34261
53959 93651
43471 52969
7164 65959
21970 88841
50093 25435
30626 14841
62441 41673
94721 74311
34041 43790
71461 53651
27500 88516
92401 25181
3345 76681
72465 99942
44573 4531
35361 87965
19873 48449
21598 40181
49313 92461
67014 39777
97814 19699
7020 42505
35777 93919
80065 63175
34157 38733
70711 22851
68133 93928
74489 58653
32252 78421
23309 24439
64603 70655
95448 18289
40565 8691
95251 13075
32449 84985
88266 76183
60956 1789
81301 79265
7009 55711
10969 81301
37409 39013
60446 43676
12771 78411
82046 36865
14261 85737
96221 53401
52699 50401
88629 51901
54251 31575
45128 1411
45296 83143
7785 99190
91226 50341
97713 2031
80232 2105
73053 32490
68830 54421
4101 54383
2826 92076
11001 88364
19690 49831
3318 69847
54812 70529
88137 79027
38241 16747
35445 24633
22537 91097
60173 76185
2990 2423
65011 15799
13937 92102
71717 19215
333 91541
72585 14033
14097 10559
71776 85121
94495 90105
42601 55231
10596 18496
10241 12597
3616 45977
24936 64545
41821 20683
82623 64
8026 1315
68233 97826
26297 26809
71581 53993
12361 43675
30001 97176
51093 59290
66457 9809
37181 29824
36801 62352
39809 33309
41775 88395
26498 37743
93709 62789
74211 31249
7541 33387
47065 59673
39137 22883
98809 29201
18911 94201
50796 36223
78461 63991
46777 97503
15361 56001
55485 22514
3625 57984
60796 33822
68818 42473
1972 65503
44086 3641
67896 78683
81098 16109
32791 59841
37254 13826
89981 20063
7784 20031
79851 83401
28526 17518
11415 42505
81837 15647
91697 46477
33859 11713
43071 89633
82355 78292
90951 67021
74759 90607
79285 28183
87413 32159
46433 58081
74136 88364
79649 13939
8621 88096
23585 4625
7476 15843
88857 59041
34901 25953
58836 7969
24313 32195
8181 25541
2009 22018
36471 11601
14649 50121
92395 44396
43611 19737
72726 72963
58439 1935
69285 98355
94745 69581
78929 78621
81306 49813
72761 98041
7137 54146
17873 61842
18845 92617
12561 727
75581 94377
18909 76067
22785 69373
13035 62001
48353 36050
30168 24796
84033 69946
3771 11776
32753 75685
34922 60793
50683 11745
14654 9050
7591 80913
23465 37023
69955 48467
39777 58275
40269 39836
9429 26248
31285 44227
80216 60001
90764 99886
7301 45771
25621 7086
81841 66433
19041 73443
58247 20870
93665 35091
85407 47905
83335 49875
38081 92016
23951 45625
24301 1581
47986 63512
20987 88441
7701 39523
89873 8916
73219 34273
46782 82793
22425 94901
12157 95720
98721 42165
67355 19105
85459 97504
11101 3607
60267 92701
89005 26372
85705 97229
21222 93537
10562 71713
47871 92521
95482 7005
93691 37681
15945 90113
77402 27396
90345 66901
55345 64570
41450 61376
24301 12919
69974 50201
78206 96247
8075 21996
58509 87787
20713 28741
961 30796
27127 25812
52796 55643
46037 13251
82881 42313
46192 27062
31201 64174
82157 585
79040 17155
70692 89850
77533 57235
57425 98211
55071 17491
6531 59381
41487 19032
88315 37379
45111 73001
20751 64549
38645 80380
30904 17377
63227 85302
38721 49348
9775 80244
35301 68025
52941 8051
90862 6374
15713 65339
67985 34917
7233 6914
88813 6243
88356 7431
57007 26681
40016 75541
35215 57829
6241 36803
11034 65101
80259 55828
42177 12839
79581 4460
77889 96787
66286 40609
37961 30025
30489 76361
46055 53949
64349 4631
59234 23446
97681 13371
27091 77525
40993 48095
80611 6971
16434 24673
21324 75917
527 15448
4367 77086
7062 83776
43357 78552
27201 43997
821 51001
76801 8068
53949 44977
13360 89463
60051 21003
39629 34464
55096 41487
79333 33892
32495 708
95861 61145
13179 90751
50041 89641
66354 77858
35292 42381
67653 36476
90225 90130
8681 11264
39864 72976
26996 71056
10849 5345
48633 70561
17303 33953
83289 15031
61281 31987
91417 80471
69401 18768
35794 58483
94101 45101
33273 27313
13301 721
22395 54671
52405 18537
78737 93601
42947 29485
73360 24977
47741 92448
58495 89137
58338 5430
92851 42283
79703 22719
97249 12501
25108 14931
12395 28997
66341 75187
78643 1821
65366 86881
97377 84651
10529 96621
1525 98533
23410 90329
45569 20841
36489 45257
46881 21069
22697 12554
88643 23653
89761 37483
1496 75355
31089 65491
27073 59049
32746 97369
27517 69229
55578 54877
92056 80539
52080 61651
51616 14195
13417 40766
29529 10676
80223 35177
6583 65331
68871 60454
61816 74625
15137 95751
72177 87041
48333 76981
89096 4281
76064 84577
79649 36857
10001 73915
20863 92993
51907 47521
15837 16445
77303 89390
1129 56466
55469 50951
32788 87603
18939 33091
57973 67801
37694 51845
18977 5790
17121 61364
45691 84441
11467 4622
40913 85473
14583 1351
47733 95869
60263 83225
3927 1437
6401 70941
55388 10065
67774 82861
16957 43647
43201 5204
83900 91106
28921 85306
6251 729
17281 85996
54849 39907
97226 66717
99168 3551
35969 59
73647 87161
45999 72897
92193 58529
63892 65311
67981 96033
51491 20791
53018 94044
78920 62969
91838 73061
42273 41980
50329 89727
13753 68297
10638 97153
5222 6604
56653 14117
27286 44421
45945 87681
12436 6086
87829 70148
7628 20377
69003 28151
16751 30886
57319 60441
72554 51165
67856 64287
73574 48417
45677 6709
80621 21594
72389 48881
93137 401
69779 36257
43528 69593
23750 17181
68531 56701
42404 1921
23617 16193
97505 80489
43129 72866
41257 84545
62431 26817
39228 61215
98145 30890
74614 26401
34001 82149
47776 25626
12709 2061
60912 7341
50645 92950
46226 63205
32457 48324
58241 44946
97025 29799
65799 51177
83199 31613
70823 32907
4301 10499
61896 83088
1332 9166
229 118
418 138
186 61
489 55
69 373
255 371
377 249
307 288
177 376
326 308
216 180
17 174

Output for test 7

1447540.93

Input for test 8

800 100
24486 96001
64101 76030
4014 35615
44995 24021
58915 41127
82381 77925
9964 89951
25123 82231
25135 51091
30072 51264
96865 42755
6331 77028
54361 91441
67947 98057
69307 53695
78063 78991
78057 41623
16049 60399
96161 68787
98789 21140
73039 171
8945 50161
60389 91833
86646 9641
58281 88277
34683 81413
16789 81311
64575 79571
56953 84781
8111 1177
18059 90469
58743 17804
5943 4055
88527 14817
39311 33002
34465 67729
81139 81153
36787 63461
2525 33277
33171 42029
53059 83993
16433 90046
60729 10301
59793 7375
86235 17501
8631 11430
80185 47681
80377 76650
71139 26200
5796 92051
49329 81462
19027 20732
2768 15301
68046 93347
54721 79221
73391 57473
20137 93960
30074 81441
94686 12297
47151 78810
45545 99497
58553 3536
92947 59507
20715 73110
9761 92073
74720 61791
61567 41810
51553 69702
86913 30172
51138 98561
94881 36768
61155 97262
68135 81921
99010 46217
42441 1616
26971 66364
5102 20265
80919 70896
73121 82797
52643 79091
77595 6833
14551 85143
97865 20305
82675 56431
18149 28132
81821 29241
21449 22481
61816 89441
69793 96851
90851 1621
43251 53030
7876 5261
93232 88262
79393 17601
22543 1133
13417 76393
35701 82425
76785 32864
51763 51921
76912 47601
89045 55941
49678 31626
72126 69911
63238 21781
24441 64317
27799 67235
85059 73441
6754 57833
33552 29979
51001 96781
39899 15181
2571 59901
65277 97221
37871 31017
43240 93589
34693 9857
93541 56242
27055 69257
53751 18329
35115 23521
26321 491
98299 94933
1233 52193
96801 52263
5565 90296
38705 53176
73641 49676
34961 59767
76645 879
29337 92616
75701 77825
95753 58328
13156 71661
59892 93001
36520 56962
9311 2065
82666 4215
60201 86017
48591 75763
9189 34076
49792 83605
32226 38377
60196 98617
64235 33145
87136 47722
32271 80018
38281 66547
140 25125
18837 63537
87089 15949
2193 96325
48341 13463
96841 18601
51650 28140
9343 99266
19835 54271
57501 85217
41828 52849
32801 28393
12401 33009
69693 70623
98157 18071
62100 23412
24454 41659
79698 44856
94007 88585
95777 87225
7033 70177
50852 39265
97497 67785
33967 60211
74771 7625
73998 6077
16183 93950
85275 22007
7585 32313
25105 41346
10817 96335
92795 24369
43021 84457
32209 99361
3105 70162
23801 90250
54841 83105
44001 50170
74941 93277
32289 55697
52536 10383
82337 75953
4354 74179
81274 17644
79045 88233
69001 90212
56969 7201
18946 96511
2033 47077
55977 65681
3531 72749
67609 99591
18961 62807
86241 75841
76619 11791
71201 32615
58715 1764
83941 24997
15982 50100
38518 33376
19013 43561
48905 46157
80541 73769
71678 64875
72473 69257
7233 84889
7633 81297
38961 59941
92665 84993
66783 42160
67721 47588
29833 40507
62049 75999
76417 80966
53345 35161
99767 44559
22231 11002
6110 17930
81601 62362
86221 41397
83153 72641
12641 39219
50776 31021
1678 55706
66673 13405
90345 58121
61162 9011
36374 47043
41752 6833
87141 7523
31377 63809
77909 91525
97101 61519
65810 42502
25221 45629
39466 27810
5558 20406
58141 76321
81211 29324
80615 17609
1567 84209
72201 47064
96941 30545
57769 98781
48937 23845
59360 44588
90213 94689
84316 90676
14911 93396
46145 60605
88397 48865
99555 6309
63757 43449
29433 64989
20121 83687
81356 30333
4837 43773
46610 54089
69893 84667
67800 10657
1420 92299
46602 92841
69266 53865
76239 39481
57869 46779
49471 7499
77685 89799
9545 82353
84149 10993
82091 64993
98196 10227
17081 81972
52078 89685
35901 87110
54201 16127
14198 27045
13431 33125
35177 95037
94901 70103
55713 64663
5635 47179
14216 2301
44536 97593
37081 37977
96796 79237
10701 14393
16594 66669
94157 29416
19739 73011
78240 65549
61257 19301
65049 9041
20632 26225
22672 51885
58251 21502
2011 74106
7489 95357
26087 6153
51973 89633
32897 91251
74935 99717
41105 25911
90919 10241
38689 59371
50336 67609
95289 89061
97441 60426
84371 54728
87221 17137
391 66785
89657 96971
59009 39765
93495 81293
42781 4683
62486 95625
68301 73456
27982 22745
51557 30752
88971 86041
35705 71430
86473 17551
74981 76486
59176 51900
63382 76226
78665 7841
57908 90577
85581 63907
19045 72916
5621 40526
47041 97388
28459 59118
45676 3837
793 69088
516 4360
43933 8150
57593 56701
20532 75665
96647 1909
10342 5241
13122 90211
21515 48225
39886 78126
45450 37967
49313 21651
36073 22243
46797 84644
34153 27049
90467 18597
17402 74200
50473 10171
72367 53994
95942 14325
30150 93196
61739 13177
9716 17610
65001 46976
92573 46809
75626 95643
63921 20751
16188 40577
13021 19925
46601 88889
76667 33613
21797 57871
46852 80471
63121 86970
17266 46303
77265 62373
12237 81593
75246 35249
75521 72190
55477 4356
52001 44020
30654 79816
85024 21953
89407 58007
39921 50506
36744 56251
25253 14510
82654 2621
30092 32001
88571 53239
63409 94648
55544 51523
88309 30029
43251 68035
67929 16329
78169 89125
64430 57411
33877 6221
43333 39929
58537 1746
9581 17511
28213 57997
24756 3161
47933 99344
42785 24531
1537 54011
64075 9219
69761 88921
50545 88521
27645 87060
62320 24386
18199 20152
39739 11350
3327 57121
5253 66411
62827 81829
31432 92657
34001 56957
57823 71349
37569 34826
47933 14798
26973 87172
20289 23781
14177 87625
3351 36741
26811 78120
50629 12521
7217 13083
1645 73666
25859 23469
94313 50091
43701 76657
78721 51285
82141 22145
29705 14479
43125 95934
48789 44621
83001 40231
46313 44890
20015 54017
92561 50145
8898 79389
10045 3661
4524 71467
47391 94545
53257 78297
15441 82339
62066 19041
74234 31029
15706 2713
80407 56521
22363 53845
84209 92551
16976 67209
4201 78541
46849 84593
59072 66278
90925 90231
96546 2321
8831 53521
67218 1233
62718 87181
39721 50365
47054 33313
50661 15
2812 59301
62960 96187
95855 87501
43561 43201
95279 57201
67071 23589
73601 82843
78921 69121
50205 92167
2275 47289
81316 33045
22950 4061
40740 64222
5034 88443
79354 82989
11361 40683
54625 99101
48519 85428
61935 66000
47461 96293
26734 59326
93481 27529
12518 5840
59621 9591
15041 54195
46993 92457
99617 38585
1739 98486
32360 8195
32833 5429
52809 48308
80621 15643
12935 98129
88481 58715
14156 60485
64917 88265
16141 54435
94081 1951
61857 74950
31797 22697
32286 99297
13497 92749
67076 61507
44520 42208
47975 80716
38909 27201
20583 46023
15429 64825
90831 28092
94352 81996
50519 64941
67218 86114
39449 6395
61365 65153
20191 83193
44751 40587
98781 67265
12369 69827
58841 5061
56145 67410
97288 35296
3271 65351
99085 746
1037 19548
43301 11417
33309 39554
98905 1087
42413 59979
38526 89855
74967 28296
26761 52307
34721 35775
73265 48801
20666 69817
71317 64461
30881 75278
63249 21229
42169 66351
65785 57749
52412 88334
57921 30605
11237 22601
59433 27261
22401 89485
31101 54841
50361 93191
48875 15447
28781 92657
42805 73691
56185 11077
93946 15486
10521 49906
26550 24701
61609 35605
50306 20433
63617 75135
79038 95988
65551 79956
39605 39321
92213 49514
56574 70609
50635 36824
59791 81505
93676 24501
24626 95403
69561 30184
78741 40607
5061 6697
71821 68441
83321 98221
73219 42785
56938 44792
64335 33495
35287 53773
26619 12353
88059 52784
27501 23884
1800 11671
53211 59249
23401 57841
95691 99813
65909 62551
53211 32341
34929 73382
94745 63244
61151 84847
57101 39395
43445 93864
69267 64801
27837 27477
4353 23908
75788 98269
13514 41268
80276 62350
9237 46364
92536 34351
54957 57729
69168 40661
25761 99153
57719 29313
96651 39190
40251 60311
10637 11631
99841 70273
95081 90925
83953 64426
82457 67601
85345 39795
68979 31777
79761 89349
49321 70097
30222 59611
24917 43567
38442 4085
59079 61715
73223 7558
87349 31099
12225 36947
35776 54715
54301 88649
25865 50759
81302 70813
32591 77546
43621 33123
72201 28041
37263 54425
70393 97251
1815 3873
72851 18753
28793 58501
44122 19786
4026 48633
31207 36312
32491 45281
44681 47273
32961 53361
89741 87738
74867 31141
1077 49296
7289 41091
84331 50633
76095 20756
22193 11201
1139 79553
49853 87945
47921 14968
93706 30861
49841 97066
59482 27416
63971 43309
5563 92601
6989 97481
7153 1905
80974 71395
55634 68197
76167 20028
26411 62701
8977 25249
12569 42721
67483 191
66033 29289
17825 86651
66305 21823
34533 61781
87961 85025
57411 36099
3436 62351
87544 17801
34418 38693
16321 79846
29921 90265
48533 10889
86201 13336
66081 50453
87100 10867
61 54121
44455 34601
17751 9526
79385 18651
9606 82471
43032 3421
43023 51383
75835 57571
4161 46138
91653 88851
18602 72585
20142 57396
93058 55809
16889 22037
63710 66641
7551 46945
96433 22721
44547 24618
90473 47053
55417 89750
31951 15883
3845 56225
41693 72541
90737 46625
29058 21081
95513 17880
98417 12771
89875 26495
52411 71607
2398 41951
21994 41173
82266 82861
21676 79581
85791 87241
35868 10337
60917 83779
54657 9918
31468 28948
16739 27289
27813 90861
36645 35681
15309 9486
89346 64145
16695 87331
29218 75378
86745 63825
53837 5141
82361 55825
21121 82050
89371 7585
7387 52561
13513 35421
34325 79459
99551 22294
18064 45069
69081 82749
23753 82051
55601 86042
31596 50689
80051 86734
73113 50653
80276 14286
2545 94763
64521 13249
20457 75384
33613 56247
21487 86651
9235 90001
10791 88291
18194 37908
18193 28209
10081 81529
53815 60126
13623 27030
8251 24316
1961 83309
55374 53457
32816 96297
34121 48222
52641 37757
49341 12165
45111 89172
63189 56251
84433 54289
86929 28851
79670 716
33822 88513
12613 20425
45157 36541
49297 17321
91306 20081
24683 32718
92737 60591
43085 28705
10768 40927
33429 44897
2241 61467
81223 43802
65879 45377
65091 93870
7856 73922
29665 60240
96573 23421
79741 10748
24461 76873
4376 30721
26809 41345
80876 70296
94847 34353
73261 26785
67601 893
44357 19685
799 58701
44728 84121
24229 67720
36441 61991
40562 38399
95805 23613
67481 15045
11737 24345
25756 71152
603 510
287 142
25 703
429 342
623 248
556 435
296 346
354 36
538 721
689 147
121 596
268 472
426 448
745 351
219 64
88 395
145 400
275 603
65 513
341 299
675 607
464 510
68 178
122 603
59 610
680 406
766 158
414 784
470 127
37 737
465 520
574 597
470 529
535 405
94 485
315 328
673 104
142 441
398 253
346 699
64 582
3 106
493 685
578 148
448 228
80 88
106 424
65 333
468 395
339 262
728 657
359 596
241 571
527 717
784 771
9 396
432 295
619 601
301 233
479 363
656 790
145 746
238 710
39 186
274 676
432 565
119 206
672 568
411 255
27 33
721 203
687 695
757 523
455 490
389 730
94 157
206 542
177 2
421 587
632 772
440 677
598 650
515 644
174 699
39 29
89 669
536 95
213 355
150 763
352 614
223 39
390 82
354 196
695 485
151 63
541 564
334 85
364 302
165 219
314 709

Output for test 8

1474819.00

Input for test 9

1000 1000
842857 574913
768001 838389
126465 706661
168289 402981
115013 219758
836494 211630
635326 218497
825404 908353
814685 662185
689651 365876
938293 939473
514151 549313
846385 624901
712197 672721
415001 344998
313637 906006
793501 140481
101045 674545
209726 67331
139601 547190
517477 480166
6721 311749
118926 806965
117818 138941
492686 769613
489153 308117
58718 803495
451364 492461
459225 535629
468339 314003
154465 856566
980265 801055
562516 535441
142645 700921
456803 835972
48109 295470
89632 549604
562727 444686
494476 958425
683471 484185
238141 793463
239797 522331
521321 269654
585543 6847
857344 942113
841461 380946
892327 327425
659999 653898
542997 15361
683366 646907
880129 341437
583485 509028
46775 30921
139506 537001
656107 179793
407993 676789
183679 831692
54281 315243
149920 301681
628001 5351
239377 791153
242573 307415
837297 100916
657609 542045
731239 577580
986241 404961
901520 943615
676887 673369
431168 785757
771091 805476
166689 63692
814917 351054
502809 733663
781375 229432
707471 249772
920435 129211
571801 981807
108091 990313
842781 276146
153249 880890
666307 137031
595539 312919
747777 295240
771009 56333
864177 23266
602971 883873
465106 425025
765972 556246
267001 11025
30806 908359
932831 600675
869874 239268
491644 858564
766601 778193
748171 527521
676169 80899
143869 302529
447205 369885
28705 466371
749729 128797
319274 498801
701426 938301
201121 864721
908907 762420
753313 751518
851711 810741
605921 341217
291916 283233
819072 628281
389828 850548
269325 593651
374736 219353
774191 501309
896096 581430
458856 794117
579341 640111
588973 956609
90297 370951
377591 553013
124381 950331
907580 92191
459300 450141
697078 58813
129113 929151
924713 101290
130840 580111
61989 852937
792841 41061
676946 800963
479344 735350
717928 643509
2353 29961
870647 252150
816259 455783
101070 185771
930501 237695
739021 917565
522703 808044
517233 248065
76703 402768
675593 622025
714726 392289
265903 605623
204509 802039
145100 403457
369935 353505
182281 135481
525633 161647
321822 170782
782961 136705
84950 53183
662751 655805
550509 898861
463757 491231
643281 48271
417225 996026
640317 576986
188299 198733
932913 851446
139101 532501
600501 833285
302845 444828
852121 424921
5951 976879
390673 268032
397037 804657
903816 288626
884768 915531
473713 962970
894981 272051
134945 982247
754465 643325
845703 898861
873321 224315
22104 16449
437081 69811
433429 843897
909061 996963
421477 162103
284931 925343
130723 871265
496257 582861
907871 624023
513040 904814
403729 183986
758921 372477
687165 900125
714146 98925
727691 279125
529181 825575
465700 263152
974341 921123
436990 540419
327174 112276
44569 622399
67531 430889
42086 571425
664351 422013
38349 684974
565917 999949
60990 606555
50483 262304
167866 755697
688481 331625
156401 695157
808201 672181
193061 308571
116206 761979
524505 432897
595123 93221
269991 966607
728345 256761
626740 305210
837957 953501
428161 217422
980686 849669
136189 201320
681710 574501
249874 503551
613176 916091
63597 704185
625933 588216
579005 698493
195622 99257
288891 906977
808989 703815
309250 206801
331451 319976
219021 170857
296136 999401
467321 42769
462977 715289
250637 982821
71751 55913
459059 795672
481181 969665
743765 813096
34133 662647
342509 867888
31076 303761
61431 812321
767753 144721
197937 512337
781129 475553
568801 24849
217657 44652
459155 57401
154762 635451
956645 667457
105968 558787
206320 990251
143876 164985
469851 510945
201293 300052
790531 706673
318849 862789
974849 276003
717001 513317
618071 962585
616022 726825
645955 107046
51393 163841
15179 609633
948202 360749
35091 132080
112731 84804
775335 18394
155571 809943
903393 950071
544013 108849
49051 987315
778913 161899
449561 525956
213891 66411
127605 173404
962288 105348
758351 165686
859878 564016
208903 76313
180484 125100
681061 185026
896417 903756
53799 360601
176790 340109
380331 558881
856271 371801
616140 259691
314666 693528
768017 908668
461152 149343
94710 338698
128361 702633
883529 209124
446487 385800
155541 330877
573109 820711
132145 126675
712805 956849
552560 498391
194409 372859
359151 171446
111401 946461
60985 708912
806335 226401
604673 153417
602967 53801
158975 741235
575161 932654
129665 103681
963585 249116
369763 823231
459851 785200
619281 470225
384753 450846
693306 194361
700199 593381
400401 919379
715631 490381
157186 902921
289025 858874
568713 26905
124213 91761
684066 79274
343489 629441
78613 175725
923035 439025
466241 630737
162871 728305
81268 710792
881303 208104
816713 223051
832363 778556
340681 865509
158981 72001
764081 171756
767631 481815
634387 696047
558381 278605
984159 769601
382271 386641
814385 849330
57343 664363
924601 190499
488381 640285
713832 230741
796142 777273
54029 490321
33201 996545
570207 674888
453864 638006
178546 377161
253175 596721
374609 565947
699807 342331
426731 319131
142212 39117
417386 912777
595809 388874
504867 11619
643329 97509
401233 730491
960671 38121
636709 722831
397169 362433
670581 950081
206449 816969
563947 702920
915817 665393
704215 926995
687692 161734
538913 541149
773577 639271
511551 965889
671600 427633
938521 49044
695156 44801
357251 556357
319620 38977
580727 356581
436446 311743
701829 503527
595289 571861
645656 375158
210913 373313
490841 757202
113196 732062
548201 550497
382774 72001
783025 100734
763001 651740
460653 539376
125307 974817
883546 161115
553751 161084
977713 74207
94998 458429
72117 597231
854117 638381
97921 483000
266603 636072
412931 525126
453809 169204
44197 674641
864631 505681
679219 342126
797868 278470
846711 358074
148363 705306
270435 637881
22461 583448
959422 17275
581244 926801
702289 337026
860821 783251
546977 42425
299077 339052
164446 262262
183857 902403
216663 265968
780921 742529
883425 80589
503453 873611
604399 744961
684057 515793
391521 731277
200277 274225
904011 654645
992549 598999
560551 520741
268468 817501
707217 284191
705681 71585
496005 233869
156581 132776
661428 593581
335919 18625
945486 522049
817251 508043
664625 359233
635966 134953
421718 16545
732801 702238
744408 80091
333724 878704
948783 208395
147586 603057
392525 114127
559016 833197
916117 552451
769838 311785
356897 85721
534251 515633
798318 599297
769983 371281
418391 537411
671633 224421
960701 119685
300075 896464
704925 435281
466785 630135
41041 29855
276549 456591
601476 921857
343796 477164
896976 686476
300001 736879
28482 251533
985547 824970
605641 878858
99741 967258
480193 148435
408069 566353
29601 762617
618646 858801
838667 653131
950651 123051
197178 210577
722666 577827
244161 869801
23352 188617
367922 651401
850571 522521
576348 656241
400601 802301
331876 687977
833457 139865
846001 2902
583856 299513
492993 915075
845191 549641
984361 272474
667288 805361
947813 143716
209337 110517
489837 684133
974842 377881
230369 768026
244489 583861
267153 560605
726 466964
612913 2385
846775 652741
601057 423661
370339 188954
39901 626686
802912 686189
610414 396362
891693 169201
33036 844576
136049 318457
397001 438889
438452 580095
862849 967340
979513 772801
549823 746929
76181 28985
420416 987459
722366 360491
255271 830834
282577 412973
377620 921663
358339 939539
663823 534016
264485 478280
272937 81626
499359 263773
312326 306941
101239 196965
6601 762121
636601 989049
96625 338513
609590 711427
481312 368737
248741 261905
980217 593341
132733 509469
69601 485988
892001 599276
709741 185957
66761 318082
912213 835999
243877 606881
883163 841153
111328 469385
762971 831929
981404 963162
748560 421995
879673 215625
754115 204747
907464 515753
646081 239223
864767 866424
838101 70255
38357 156561
211919 987381
96135 854863
275774 821041
98823 848713
446871 377455
612755 257335
998654 704547
21949 488593
725101 479415
362066 434593
127733 765025
851018 504993
895929 634532
17656 834605
846431 214208
979961 215814
420501 304910
467962 272407
451001 322781
104043 83689
349839 162337
986535 528201
650836 296441
103505 189507
852849 796764
140285 679184
356141 697595
357485 416077
857289 988195
284726 308145
383206 884969
680431 641631
941442 548019
282141 837101
786278 977219
367065 922894
444225 926721
886133 439649
438753 258529
954287 423403
692465 310417
335834 297895
432603 462155
787133 905975
611991 262611
645609 283632
563849 67694
904486 330385
397874 113131
260397 269333
556986 441716
76033 789429
208009 794039
452832 311394
221123 63567
113281 316801
898625 905881
237898 453231
203641 715275
591866 793221
50173 384337
815347 17239
287768 325989
731903 294601
200481 607569
439875 951276
600874 382577
68104 286951
524625 203581
420813 830505
533575 255228
643360 295955
247719 45553
993497 124341
511119 879681
400353 390201
257577 342823
560977 835296
687101 797721
540996 826849
433656 717503
557404 883665
586936 147185
447028 613781
558340 783983
292867 963200
329596 605473
442064 913134
533317 831751
430984 966740
868185 468273
920825 475113
912020 424321
37251 63751
244035 738003
627103 255239
346745 680289
78521 841259
848722 362081
642926 221803
127663 907649
217378 288961
34723 957551
224123 766056
251461 279361
852157 168913
535153 747081
685441 312159
716337 15399
844031 656873
623643 435919
517133 681928
188475 129708
530675 351335
745457 489177
143385 784500
96581 181301
828523 550549
514688 928961
91201 556257
626297 689890
424763 126607
332101 337633
775351 788862
68878 753721
735345 629929
488121 451450
57509 889169
271972 881224
328751 151978
194038 633113
182445 327561
39031 63286
899656 586703
880736 701454
372223 498037
7959 474563
424015 605525
264629 75425
277887 421703
996851 799233
674105 330391
56431 621639
590425 922262
819346 244001
918087 588395
288321 60886
470593 431140
106581 628089
956435 804863
244377 194941
950398 194711
925953 146098
341481 257995
229793 411981
132777 539740
854601 90884
82935 860622
578012 919917
680547 252251
323752 66121
427098 936996
583629 674417
117131 522016
244807 836897
304645 568001
513311 10721
410231 965586
838017 756865
223041 634992
423402 433915
947471 967245
400775 145909
549649 447337
643676 401989
895006 643545
83009 582896
576185 490005
538125 678097
154817 354757
362624 589026
966593 439285
158049 492248
214561 612408
850581 633089
491613 2665
538024 326437
98180 975127
17025 997985
757427 833539
74866 169622
380167 184951
901847 595581
324331 694841
613058 469085
437717 69181
264736 174266
519489 318977
621519 547901
610353 81713
871776 74853
487292 783994
372663 78725
888879 640061
392767 284051
92193 784921
883441 365541
859504 353693
230071 299941
919433 819485
990601 742092
575855 804231
230414 268884
187498 467057
559747 949609
201105 179991
346412 583905
950709 641191
196609 865495
483013 961855
352784 137951
610849 19385
784405 855883
870763 347915
756277 663343
29129 467913
276241 769442
738171 404082
192077 64557
485506 191441
100077 501595
103511 706721
934726 690169
598257 344395
465836 491617
709246 389271
997497 604805
20641 930297
771669 944049
171201 571500
612199 279876
249189 259903
321771 338973
615760 472618
669406 546737
757005 790749
273777 383063
986176 729794
88153 709732
809952 644126
974686 391759
79177 796413
831713 463050
652551 834269
508260 326931
29061 804766
447686 162881
134296 829724
845966 670203
914831 161704
328049 73131
465033 985165
321189 356583
895691 148451
741681 4573
625308 756136
975821 935693
546061 823131
747391 997153
371385 59430
999086 268538
898017 485518
955664 5059
643407 803556
435975 626213
306881 347071
926933 738265
746702 18721
634046 936657
913813 1413
220476 111499
879826 685086
715183 988343
210313 479218
30363 343790
717091 45605
917669 771236
868103 18919
620131 969171
693501 624483
395025 541577
910711 256179
473082 971053
455561 304621
284849 529729
568985 639489
682935 955937
369603 900161
533961 801307
349333 242299
679645 782006
445110 691573
186690 420433
473022 213705
835533 163229
227591 302617
217001 741805
173012 233543
168937 853226
899801 68579
592873 190490
379915 412393
815089 907477
49169 646858
288569 327543
563903 872177
435847 876945
924356 152945
601341 21129
828959 396146
808217 892861
299305 793126
555578 223685
610441 294011
467427 122201
568369 371777
35466 194847
637660 898777
929197 634117
71076 236161
576225 300520
128780 614648
828515 913097
683921 305435
850431 879664
547876 576409
774201 604257
792721 763003
175261 362001
999657 172689
432897 844157
463466 395591
408417 983369
132060 707001
744177 180917
296001 291379
446722 968373
57731 351297
348197 382563
113258 381723
246956 400772
700839 832159
317193 946841
477941 150624
673885 526333
316801 795091
481333 231081
636351 302889
421109 167793
265389 108484
264483 557065
766711 745345
651867 343401
958640 541393
418689 378723
718784 551716
662817 186994
597501 859421
859057 417221
408001 921522
471016 578827
969751 64727
651121 346251
613631 451721
669337 742813
799289 49187
269046 99701
925857 796381
11889 977237
948155 273745
873993 515693
344474 471461
315430 809901
512437 209286
40341 266494
987733 625759
648101 667255
605871 679666
862897 163065
475727 425240
26433 635381
313281 631389
872413 328039
345545 794461
45103 104052
297232 156749
50546 590101
833809 928776
100336 80791
965009 90203
877341 479605
697985 555353
424214 80126
681562 107831
789569 750107
174241 425629
992793 451220
940726 470893
549458 315096
952527 635409
274488 910329
697821 880193
645282 439809
188419 825691
539611 436287
479451 23171
351474 223364
236469 21057
11173 187473
544283 390223
205633 265441
97691 157145
574983 203392
621621 895315
783271 999001
105743 258751
174021 293035
116251 312506
400941 812745
540663 980126
867311 437887
609926 229265
955311 681857
73035 986641
345105 634475
342738 206913
832871 634435
254241 362936
138985 264889
85279 315380
548698 32649
424625 783051
927351 965569
937985 256218
262172 284411
472881 553708
566 116
933 789
572 291
406 358
191 339
729 638
873 639
836 786
94 535
300 571
932 704
562 856
718 543
653 435
171 711
952 410
482 89
326 871
417 851
491 346
23 860
365 101
623 191
755 72
782 78
388 806
454 825
260 815
372 87
898 104
902 893
933 960
425 653
464 317
834 544
547 854
156 350
925 674
562 685
919 569
861 681
298 808
816 835
372 595
138 189
711 815
203 133
218 174
115 768
964 470
447 617
22 500
166 202
352 485
499 50
735 853
187 431
725 147
202 70
850 765
345 521
498 304
595 600
103 427
79 883
369 892
536 191
906 267
132 599
286 342
898 389
83 404
656 673
62 606
452 737
727 651
361 314
597 755
715 334
357 230
279 238
919 590
965 98
505 666
639 518
760 805
575 447
692 230
596 543
860 953
757 685
578 718
217 753
272 800
326 14
899 625
177 97
478 324
485 273
666 579
7 191
501 114
466 608
833 940
606 664
367 636
431 473
291 31
755 349
946 824
771 729
121 787
277 746
679 766
970 292
782 949
292 105
166 494
858 895
91 508
791 989
759 319
368 998
531 948
13 639
275 353
281 974
31 956
517 500
241 804
410 909
860 856
54 844
105 847
161 508
592 440
224 957
373 651
889 564
577 430
536 646
539 205
977 118
646 204
104 925
117 79
382 513
380 140
820 410
832 831
437 520
546 374
710 265
8 958
898 418
181 38
372 955
715 106
331 936
61 203
981 382
953 141
349 371
438 545
623 432
787 12
335 411
168 16
332 168
857 553
650 377
480 163
304 638
242 2
167 382
917 689
829 254
255 295
433 457
139 879
767 729
104 480
854 68
523 900
905 947
574 196
291 736
849 492
854 94
952 819
429 277
933 534
832 949
295 526
800 83
434 15
988 442
81 1
652 20
450 164
212 602
745 632
851 896
512 619
44 675
838 399
948 855
605 371
910 133
968 32
275 506
820 423
830 206
710 25
967 435
637 543
310 996
578 283
947 664
6 663
867 63
890 869
910 220
973 966
718 492
97 999
802 318
567 944
37 211
677 751
160 656
13 301
455 177
279 791
315 489
874 880
587 191
727 732
617 419
694 688
418 42
741 289
677 822
29 179
856 905
296 827
247 131
353 838
711 522
218 778
811 994
740 54
436 22
658 14
494 605
895 434
672 984
809 984
84 195
102 166
504 993
342 884
828 21
745 386
805 895
923 550
178 908
540 105
917 770
925 418
84 873
320 234
345 613
447 914
22 20
760 170
5 739
56 468
855 54
53 241
43 487
848 394
513 135
755 17
736 211
927 400
285 424
490 954
573 946
959 825
684 754
757 128
47 662
301 874
167 901
454 67
391 443
915 814
32 754
176 606
635 378
297 560
111 634
4 521
995 95
111 676
78 796
157 39
357 771
637 847
262 411
667 824
858 235
435 993
535 181
140 288
58 786
467 750
238 694
453 355
529 179
332 651
566 198
633 402
552 345
914 535
29 840
420 822
417 101
246 10
61 543
956 65
394 111
377 733
881 603
593 351
836 958
230 999
674 39
841 913
999 9
91 634
346 507
325 724
564 521
973 775
133 219
777 768
721 549
681 342
931 439
960 730
49 853
603 391
712 289
686 619
553 999
347 708
44 586
788 950
740 317
411 580
92 229
480 798
848 869
875 818
935 226
442 397
647 224
477 323
457 812
304 694
254 388
121 700
787 899
762 68
969 74
73 474
289 83
487 537
510 215
342 40
514 356
359 48
734 807
690 397
996 768
174 35
71 462
668 890
390 336
471 365
508 750
663 912
548 591
191 161
907 788
51 225
838 749
302 866
646 858
971 618
497 149
674 561
899 494
437 504
373 383
107 458
4 362
933 991
77 695
560 103
400 930
90 300
850 693
64 595
880 314
167 405
368 315
986 752
562 205
924 635
104 666
598 219
34 302
291 911
324 173
689 586
740 203
899 66
575 612
709 237
91 93
480 580
402 690
263 810
45 762
49 558
31 335
376 774
868 715
32 583
586 96
788 859
679 918
342 499
347 154
805 813
167 332
996 607
630 530
393 493
795 84
315 647
379 376
376 278
708 727
501 792
703 903
191 426
594 66
98 910
280 175
656 142
621 80
388 55
165 692
768 585
420 5
580 990
916 140
271 441
914 379
234 961
289 100
579 582
92 857
968 92
334 756
766 525
196 903
984 740
429 862
515 127
225 340
122 244
488 811
701 464
308 696
815 691
578 558
296 112
637 946
408 172
476 415
446 829
492 51
696 509
160 561
268 718
905 353
38 545
489 405
578 338
876 917
252 686
273 981
494 895
925 973
690 455
754 665
209 404
110 218
92 459
870 142
625 912
620 59
311 364
854 2
549 312
762 729
905 825
463 601
989 996
349 26
742 116
528 923
303 162
809 854
555 21
149 555
691 354
690 620
47 117
832 50
1000 425
572 806
717 164
243 322
404 575
692 409
844 44
703 899
16 272
509 86
894 804
367 586
73 414
668 483
933 326
749 61
281 206
76 499
57 96
21 576
100 511
899 410
627 927
725 675
68 926
827 26
733 287
972 81
349 788
193 472
80 220
712 147
553 278
737 376
109 957
285 627
637 244
913 461
380 700
357 626
218 571
73 698
352 895
954 258
365 660
906 468
417 834
366 484
408 450
180 989
945 954
532 875
615 239
302 514
975 403
668 263
195 448
186 646
615 924
387 396
706 469
606 957
528 214
441 385
709 626
724 338
524 240
105 17
833 448
330 969
404 182
276 396
463 588
99 94
273 541
350 375
925 215
21 484
580 208
976 688
522 197
849 639
624 302
892 347
133 382
190 675
546 426
876 432
758 512
374 482
200 858
4 139
307 923
807 737
631 377
787 834
485 579
499 556
443 573
558 227
785 810
1 462
867 330
941 843
784 532
34 466
618 861
588 768
951 337
317 389
855 385
3 632
135 214
243 969
766 357
614 383
870 524
579 611
253 795
254 237
980 983
32 150
872 939
582 102
383 64
294 94
13 839
63 184
816 332
648 206
729 133
348 841
668 338
901 851
641 600
143 518
292 457
710 622
961 895
82 885
869 897
946 422
289 452
719 196
840 653
139 115
891 254
361 527
195 863
638 124
623 695
784 190
166 107
646 651
935 399
729 157
711 955
410 691
683 343
268 739
254 226
138 921
630 479
564 131
970 193
854 360
910 369
362 590
787 573
808 987
496 531
170 558
414 615
981 439
82 577
317 412
380 818
695 366
440 976
645 476
554 217
846 166
568 389
372 116
307 518
858 599
237 780
438 328
985 508
883 345
496 553
18 953
736 990
90 876
706 787
909 449
403 614
301 133
547 91
391 305
917 399
622 136
566 42
35 772
706 827
573 145
51 848
67 161
115 94
457 857
700 894
899 540
317 553
603 303
616 293
1 757
474 696
156 996
547 316
316 24
55 20
593 718
460 678
9 900
813 737
934 935
742 617
471 532
992 761
833 699
735 144
172 369
179 144
370 493
364 315
710 822
17 558
26 930
859 202
163 402
557 784
817 644
575 989
97 113
700 455
461 257
912 207
344 939
126 271
410 458
16 854
891 500
80 169
37 92
199 149
626 499
653 890
560 42
64 146
490 499
144 642
890 665
578 984
803 797
987 630
348 867
696 158
377 692
236 143
260 500
90 958
109 319
67 504
317 864
889 631
673 506
301 355
517 827
751 547
615 638
100 261
646 215
412 90
3 396
909 253
790 130
954 942
332 822
808 329
167 62
154 164
519 319
883 650
832 327
565 449
460 989
607 531
234 448
292 691
606 446
98 70
348 711
408 820
327 872
852 326
351 36
547 571
907 416
338 838
554 733
509 346
488 444
854 529
967 421
352 873
644 737
468 184
348 649
116 953
975 326
214 15
340 938
644 850
29 110
386 792
331 62
495 301
469 730
687 670
862 510
959 187
581 301
723 211
440 569
630 340
395 710
576 635
462 832
604 409
925 849
946 871
740 776
250 19
946 103
459 323
397 307
371 129
191 929
71 24
592 543
157 926
787 313
656 523
813 766
244 529
876 378
443 460
748 860
624 611
544 955
257 720
679 780
426 68
100 319
152 519
74 396
954 991
432 328
679 734
578 772
964 665
9 271
805 502
556 675
583 598
894 206
139 276
41 722
85 476
403 462
413 919
248 862
701 758
385 473
837 349
172 26
52 378
996 474
696 430
754 867
752 372
476 912
431 735
213 299
963 73
581 487
503 633
706 431
662 324
246 606
58 239
940 225
916 172
822 225
284 468
400 998
339 500
314 961
966 866
154 200
30 378
888 512
574 932
430 269
757 192
464 646
541 69
152 279
315 190
246 134
704 95
710 610
135 422
745 305
776 693
448 258
836 623
358 98
514 273
102 530
722 275
262 808
456 223
474 13
898 449
876 872
597 815
58 697
126 755
112 728
397 495
376 823
822 145
871 333
483 975
866 813
948 124
408 982
705 644
570 4
897 140
328 479
108 693
286 698
110 987
143 615
404 113
913 697
316 224
82 905
840 311
720 934
180 700
519 47
465 300

Output for test 9

2599415.08

Input for test 10

1000 100
734784 990052
606221 185447
118082 247133
567551 736631
686306 565577
932077 801527
812161 460341
642474 152793
772001 660531
96835 318451
833542 625005
136746 481973
29301 676196
40807 495265
725274 604536
882925 358897
5937 248151
856189 71045
28159 90141
433481 999433
647137 599179
236953 751241
763316 523981
52442 826031
34753 856171
274681 154363
214517 841296
231763 323201
365045 11181
733609 267874
892708 326047
663785 974761
176309 258199
309259 717003
115034 469967
296161 378791
680736 588825
179301 230538
906876 931905
61725 882145
796435 691653
282220 668846
871281 125264
976376 244716
426509 640065
398943 990138
325333 86897
939404 863052
58134 259425
817903 907133
831729 605537
383959 935809
148926 796381
150833 870626
983907 897281
845689 786649
828301 650173
880958 909996
310073 311570
220629 698857
508871 483275
109218 885921
759141 472353
100369 597731
217241 812557
756675 191361
791401 720391
196893 657941
53157 567771
380661 811289
647106 823961
719630 723385
817141 201479
26787 166665
181549 679401
438897 517026
847961 639721
601794 342689
937149 973835
284537 716207
364541 910917
353011 801261
39715 756951
779073 808029
126411 786105
819953 183500
374001 28626
604087 319657
266657 503747
846482 296114
934691 740611
882197 810161
971741 175263
144320 214951
573093 826511
375971 494255
625691 601286
465461 634175
869491 807357
168216 527338
922591 904597
143697 180777
685081 245593
902337 530011
134323 839899
278977 311348
828853 285139
379466 36345
415091 703045
369637 721161
78176 922041
188157 517376
681641 298211
797147 865667
577583 23489
512283 68001
284273 561877
891067 433273
205686 364181
613181 331841
273278 604261
117601 302570
175585 903624
603493 845985
977213 641377
158357 811547
531801 340373
442741 426508
744563 48857
77805 231449
106891 772645
738511 855629
311821 27131
146175 140887
854475 10559
764250 595353
402751 405847
55496 319141
578261 582406
695257 777457
638061 611709
459078 940629
392180 51839
941473 272481
255281 806034
567351 554323
747309 949926
734185 782295
489946 78045
877500 189055
31201 890169
648293 651178
945 886441
34489 685667
752875 753487
700664 431581
312997 748513
904111 776525
110375 333779
530819 178066
519569 664791
343965 536897
434895 558033
907821 1039
160217 905361
484257 298201
250397 435553
567435 673226
167213 950973
277789 395733
262822 516730
862229 57768
282209 904001
256719 869024
379441 42624
788409 956659
951895 354234
425301 897053
697801 260837
271409 510246
114709 504239
987065 563527
316642 286313
149511 487180
308973 973875
931541 88409
776372 68267
336379 75705
758023 394567
889305 165079
717182 459585
549756 45633
384461 807657
274578 505522
799441 922090
278505 545341
898191 504065
723441 912436
476809 984698
957022 429761
605109 681889
879726 141967
970163 880945
228457 914010
353027 502421
51011 3795
480293 772498
654324 630486
327329 319972
995265 279136
636433 58761
184226 216234
304331 446401
386887 119025
935749 829825
925625 445683
580093 641285
969453 520119
515495 310176
413523 741429
284797 685102
374721 669769
135728 928763
680666 787381
731261 785957
223557 181841
259799 582341
292105 338305
643429 676478
134297 615881
544886 155839
87329 61593
961267 302361
227373 835186
563881 50625
321213 381601
765125 232129
871567 168366
94034 669545
94609 625462
712289 644855
504593 842980
561356 348885
511806 415176
186688 408351
922274 618692
211395 783758
342863 481049
368896 447999
934367 922813
236159 717422
728749 89873
296069 420481
149096 949401
13403 401455
578385 590589
509753 364919
974054 201075
979457 431033
626869 939757
663369 266153
628411 135396
227003 132339
292426 191884
45656 852937
759769 185201
568641 877036
565101 481141
76119 671241
139205 866347
476377 955521
400559 982569
351329 374913
534577 553028
465866 756865
851797 146559
739243 480664
774866 291986
749521 85785
317915 491121
852066 8415
90264 685969
184549 462889
774801 400521
53755 26903
334550 560041
413533 254519
574663 850317
657486 60184
17085 403097
107867 623255
110608 503633
219228 290221
18405 999119
172757 988263
578451 748228
891711 839513
127873 718540
535883 218009
849281 74732
822055 554645
13104 436825
889089 590004
42496 623241
385707 932043
905410 39956
625881 332001
302931 450309
197350 23273
503921 722825
276161 673437
495917 728751
11089 126977
469241 742873
631331 183340
841077 830441
700855 690736
219545 739031
85351 867561
886391 410079
880549 359552
649579 213309
652625 541801
912426 277743
174147 282225
798861 686940
485081 912589
406126 50584
107968 603881
964681 226451
668306 433981
632918 23546
981601 832273
861956 23822
541521 152442
143073 48407
812776 642553
825352 599873
137413 322747
452592 999681
192645 768935
760737 776629
903601 815418
583251 242747
462015 700304
719293 366843
928650 649409
214311 938249
721592 274161
298259 996614
370291 195095
126849 969726
127061 604606
823939 66514
946176 905671
869559 87106
496150 810083
541289 677451
765 339761
463521 378531
57877 211501
913617 335711
346081 774885
591076 409393
720751 609589
185556 159460
160801 980649
59791 218977
23783 762101
248901 762261
18072 355833
358075 687145
396329 667105
803780 112331
386443 874672
86297 564376
285125 503462
378562 853796
797167 923651
137759 449121
343741 202111
929877 876779
394826 103151
6017 373769
291917 314289
286705 817696
40801 789141
675933 776631
905935 321851
340701 253681
84085 218891
418133 668307
184541 983761
286171 660168
717392 529499
872720 357569
942585 975851
819671 376628
218090 89397
855846 669328
162027 357981
93561 44561
5859 391441
582943 72353
535297 385937
959819 521881
423801 142864
251657 503201
533385 260601
553126 339035
299931 778739
263961 405061
18020 669505
773599 285731
654921 123745
659285 123501
142059 756071
930459 506901
343813 726517
137826 711053
849865 970613
290617 347021
844665 530937
507051 860641
440570 610171
284902 310406
868149 214805
557798 782136
299493 34401
329913 949706
896305 494768
735169 540071
979177 785793
790651 472149
572131 822578
382081 320446
678133 792018
270485 215703
433615 104571
956843 563721
849538 601949
109435 591931
228157 799698
814741 408121
61271 970165
775661 941148
500781 569249
917117 694471
22201 392217
65073 138801
507129 465377
310448 272651
820638 533551
812061 670213
267661 527226
290061 874222
292605 967473
850337 417706
865441 794291
94465 706626
348759 397753
387809 151641
266515 556298
873816 27649
994525 649048
658579 289306
997025 259101
714543 214338
860313 728182
300725 96009
366421 765975
62661 707591
27911 872068
21113 415898
950149 937361
139889 475757
877776 564717
791297 950991
772353 764921
72098 844181
860778 148581
668895 287570
775081 294689
284253 901837
900261 692871
35793 954821
293952 248349
51121 833815
417326 625829
617161 4711
369674 98828
764779 43177
15601 637321
29073 931145
843956 192465
89431 91685
842506 298673
273889 913889
7199 530209
55647 830884
912076 653158
714501 957201
513261 531969
763675 107255
952749 523134
941729 17839
966001 40941
283501 79761
14501 115769
267974 778441
55801 862100
951211 92842
499708 587478
58929 849204
709455 662694
647526 651211
471039 456157
478706 617917
68670 829151
941673 609017
759693 413391
723267 799015
128709 112853
590171 40277
711827 372781
117685 296842
280272 546609
273281 867451
482207 248551
343517 798566
266697 964481
596507 299741
284516 489706
680376 935460
81929 293553
431663 889312
446167 937081
317349 830617
698109 60437
226517 299793
629516 356047
95796 157793
546841 382681
672756 476987
66301 139681
256609 929637
568097 312069
128841 297443
482289 272357
198761 377581
628121 376052
317971 191201
576979 561515
747387 728657
921329 223347
656457 786828
400411 743221
376941 654557
32407 946991
133751 325696
36841 430447
92777 72523
574570 343001
291988 969521
927455 200975
935593 130049
951149 757933
515521 125551
408196 663681
876673 546791
882109 804151
69734 803817
444711 682445
82497 388485
107590 997163
589821 469829
333901 432700
165025 509441
127321 412503
688249 797297
803137 771041
525965 25159
755236 166301
967505 569841
757697 797595
897212 907228
429649 557490
619941 258546
522917 460637
319393 441636
16273 114673
926201 352561
901137 406990
417649 896090
702036 463432
939545 207501
220037 289001
985005 17321
169281 133939
449935 464471
47766 489901
885940 517921
281397 659377
433811 798561
727944 578222
626506 755875
568649 650385
131293 459601
835056 48631
876193 418467
712017 372015
470861 610370
36551 694977
963061 791303
541701 295221
334161 119941
171441 320301
668418 284113
184443 13609
845641 502665
145483 446033
926825 241163
517226 14001
827913 154684
108851 210734
347556 340441
808561 464628
90869 741657
157897 941251
446626 79003
252945 292876
39893 128281
9641 915937
730777 431963
327384 378606
395219 749281
655945 860277
584905 327129
109499 875557
973039 598768
415221 998379
984561 550719
851255 651651
59556 977097
94033 190576
757884 647221
168505 57597
691401 275399
769001 74363
219581 56926
616686 788811
448274 948849
206693 903545
105139 805275
125171 376979
421286 91545
838055 55820
721891 646643
851077 40279
986190 523731
618801 143937
33346 394971
997053 83317
737549 767586
836532 907731
135621 660775
894337 595201
550401 970413
259476 71689
986321 589051
500225 122641
689321 133586
35182 109730
165469 729831
247009 158939
819341 576691
627409 2897
967361 624312
619995 256857
38091 964946
513621 416685
664819 959301
714448 96897
488193 624936
89481 680610
708497 505449
700753 865881
716713 364693
850257 203111
609349 634931
327375 948024
332426 308542
488275 762804
613871 769160
543531 745866
195773 265968
277805 547896
790022 944132
273839 335241
995695 91129
200689 495348
133392 86401
421199 542043
674711 422135
302804 585781
839959 814685
934081 908599
883185 252545
39166 326663
819958 977001
882641 874691
315017 671829
177171 569566
860473 290167
216704 718981
689408 68362
147501 913949
24249 227430
660121 626851
810423 285190
214239 263717
652903 310313
920451 337081
686507 940546
607886 88471
344973 381310
424996 876233
188432 156581
341121 913829
61970 212799
349705 162977
115668 293541
70176 549684
639541 639947
953977 604201
953298 687935
98625 42945
965766 400616
466689 743217
36761 441217
470243 352567
459601 290916
63733 449639
638657 122351
600049 824113
635213 7565
994977 312857
584826 73041
589684 22980
720857 51061
670155 852527
12549 794254
166471 78751
576947 574161
431251 767989
285263 267777
36283 88001
775107 563329
363141 954201
257782 667775
219493 14697
643865 660497
301111 173113
619069 215761
275001 856713
498435 315660
451090 717837
71449 604417
372243 629535
129241 450121
900731 691829
741121 928916
703032 487591
480123 802041
999203 645094
339329 271264
403529 412746
974748 730405
703621 449601
891571 42133
292310 184107
477313 522595
10466 774425
373237 67303
58136 912113
451729 150913
158255 86974
771176 410979
289544 825233
431905 498113
2552 893790
678561 729881
445001 812386
124401 116606
772638 720179
536871 491801
696956 460125
809211 912343
93613 961323
17173 124275
752989 708733
527666 576295
603921 668585
107635 970653
882603 525089
397085 163421
170032 533901
589715 986425
891041 3357
652451 748521
50886 549531
293307 974668
373857 654601
953501 660759
722517 179931
367569 994161
401147 535849
412199 69713
733637 119643
924791 689669
22385 796161
497441 998924
172725 121089
358545 859033
257441 155660
449573 718069
92080 125705
563153 47401
878049 377570
374979 964099
670533 30171
152811 669973
766926 150917
539447 269601
394009 17906
697709 60251
210997 502085
393068 930171
773666 473481
148865 984516
669251 628391
68323 591253
557515 774073
500737 93258
747809 897193
532995 575553
744993 803661
937165 939820
594901 146307
44441 101945
185473 173594
255185 134593
648065 804693
592001 877783
902147 696880
196105 150589
561905 94401
834445 663013
29441 445857
402849 44601
621656 645043
146684 620593
176641 122331
591201 936686
443025 291587
136166 430333
446965 998104
898797 542762
101585 258339
298597 856901
253793 13789
245953 194408
833721 348433
750559 241143
846401 764024
844088 219585
745184 604590
322433 281857
783632 123301
51371 76433
435545 567561
405806 92081
845033 627259
531521 588911
367226 219493
264497 204931
262611 515899
166629 528109
185896 192569
242335 535865
785281 672449
794817 601057
194569 214905
846401 253119
643593 256197
720368 195521
899220 854528
606145 150481
882896 683721
187241 433393
35877 636089
582010 667146
778049 998677
516985 28405
833708 374683
137513 7169
470161 697691
156737 650113
628454 323879
877614 502473
710644 137561
534990 769253
79377 471552
508436 893709
211521 208809
687041 578541
453251 907329
624091 394747
233179 237137
853199 168301
765082 463498
68048 601361
453003 865711
611831 606869
33604 272633
261105 961331
373873 679751
968655 243393
907969 528857
895026 905862
119821 66651
222373 205441
22559 177021
947313 536746
422849 961079
93865 162781
445919 205069
616133 750449
970005 870917
793721 965432
473721 477864
647537 816157
124437 614138
761190 500029
573398 367585
848001 141103
11836 844177
865453 657551
120497 795961
381601 245061
20258 983913
448879 884033
610402 179752
383577 620001
6049 539737
384401 258681
245425 202795
779946 233561
806638 857930
214617 593937
600185 14141
938973 775744
916008 637225
54561 125938
543951 127012
697245 587846
319177 173251
234297 895478
746581 218115
336599 105409
306467 422186
295721 150578
367581 47029
705762 507481
309381 697476
350653 163301
901029 836381
344209 923981
979646 119081
840545 466922
904766 758548
108406 488069
229802 95801
132011 907661
503276 738981
482401 630749
610898 562265
50001 951645
279849 525462
605320 907011
198917 211583
828321 679155
329493 954095
932271 763581
813961 637722
254556 731165
938936 560574
375713 923646
423246 4889
266017 876641
252 615
877 132
933 528
657 670
634 492
472 100
685 241
543 413
814 632
97 378
76 485
106 7
946 98
379 251
543 645
373 549
697 423
330 480
330 454
640 880
427 861
887 837
600 74
406 943
757 513
785 883
480 183
21 606
630 74
975 70
194 87
50 969
379 3
231 568
702 158
946 388
140 309
690 629
254 911
233 743
877 907
717 301
822 704
911 338
367 60
410 526
251 161
662 909
892 469
509 575
714 305
309 179
406 292
240 429
212 9
520 818
113 806
343 322
697 782
454 429
676 314
108 1
897 43
961 467
444 459
596 931
492 237
818 413
704 98
328 981
972 70
579 819
102 802
309 887
462 371
683 975
461 922
997 599
173 197
357 144
481 519
124 92
326 820
913 657
291 615
787 284
725 479
145 336
406 319
768 735
102 173
213 479
635 38
44 449
117 232
376 550
301 720
996 75
664 292
457 351

Output for test 10

17350188.63