2 6
0 0 4 2 0 4 2 6 0 8
2 6
0 0 4 2 0 4 8 6 0 8
2 10
0 0 4 2 0 4 8 6 0 8
2 200
0 0 1800 0 931 233 1931 233 1012 1004
2 2000
0 0 1800 0 931 233 1931 233 1012 1004
2 600
0 0 1800 0 931 233 1931 233 1012 1004
2 800
0 0 1800 0 931 233 1931 233 1012 1004
2 1000
0 0 1800 0 931 233 1931 233 1012 1004
2 1200
0 0 1800 0 931 233 1931 233 1012 1004
2 1400
0 0 1800 0 931 233 1931 233 1012 1004
2 1600
0 0 1800 0 931 233 1931 233 1012 1004
2 1800
0 0 1800 0 931 233 1931 233 1012 1004
2 1
0 0 1800 0 931 233 1931 233 1012 1004
4 267
120 100 190 80 130 60 170 20 90 40 70 0 20 70 0 60 90 150
4 217
120 100 190 80 130 60 170 20 90 40 70 0 20 70 0 60 90 150
4 167
120 100 190 80 130 60 170 20 90 40 70 0 20 70 0 60 90 150
4 117
120 100 190 80 130 60 170 20 90 40 70 0 20 70 0 60 90 150
4 67
120 100 190 80 130 60 170 20 90 40 70 0 20 70 0 60 90 150
50 3000
0 10000 1540 9954 -3 9939 355 9928 -2 9878 1216 9876 -3 9817 2587 9786 -1 9756 968 9721 4 9695 790 9685 -2 9634 1146 9588 -9 9573 236 9534 2 9512 2366 9503 -7 9451 924 9415 -5 9390 2338 9351 -10 9329 2307 9284 4 9268 2510 9259 7 9207 126 9197 0 9146 223 9118 -8 9085 903 9078 -5 9024 3032 8982 -6 8963 2772 8944 10 8902 3071 8897 -2 8841 1687 8802 -10 8780 2964 8733 -6 8719 1748 8686 -9 8658 860 8615 -8 8597 1607 8562 3 8536 2062 8499 9 8475 2011 8442 8 8414 227 8387 -7 8353 2172 8314 4 8292 1889 8269 -7 8231 1845 8225 -10 8170 2985 8146 7 8109 1086 8071 1 8048 2874 8019 -7 7987 505 7981 10 7926 260 7876 0 7865 676 7850 -2 7804 2911 7775 2 7743 1612 7718 -1 7682 2436 7672 7 7621 137 7613 -2 7560 2708 7516 -8 7499 2648 7480 -5 7438 2577 7409 -1 7377 2958 7331 10 7316 526 7296 -9 7255 1824 7205 -7 7194 662 7187 -5 7133 2895 7132 -3 7072 2567 7057 0 7011 970 7002 -2 6950
50 3000
0 10000 1516 9910 69 9824 1013 9728 -118 9630 2687 9627 1446 9578 2467 9525 1721 9496 3364 9489 1710 9390 2546 9309 -401 9252 1117 9155 -1783 9123 -121 9069 -2851 9023 -2469 8959 -5237 8946 -5059 8895 -8091 8853 -6320 8803 -6891 8765 -4686 8682 -6156 8603 -3841 8582 -4305 8520 -3406 8499 -4189 8442 -3810 8425 -6149 8421 -4331 8347 -6437 8269 -5473 8195 -7636 8129 -5895 8113 -6189 8030 -6030 7986 -6230 7956 -4735 7897 -6347 7875 -5354 7808 -7879 7721 300000 7698 -7879 3721 -5332 2587 -6786 2513 -3959 2426 -6903 2328 -4868 2294 -6607 2204 -5426 2198 -7285 2120 -4424 2101 -7171 2079 -5940 1982 -6294 1897 -3445 1847 -6358 1787 -4195 1714 -4508 1639 -3269 1581 -4327 1576 -3860 1532 -6202 1445 -4845 1404 -6786 1378 -4436 1369 -6101 1339 -4198 1275 -4343 1177 -3223 1120 -4729 1063 -4513 1017 -5394 975 -5004 965 -6010 952 -3388 941 -4439 874 -4136 813 -5482 749 -2849 746 -5517 646 -3025 621 -4470 598 -3835 528 -3944 470 -2833 394 -5611 386 -5082 316 -7547 223 -6468 177 -7359 122 -6791 76 -7667 -10 -6137 -88 -8120 -94 -5224 -105 -5405 -142 -3291 -184 -3855 -828
50 3000
0 10000 1516 9910 69 9824 1013 9728 -118 9630 2687 9627 1446 9578 2467 9525 1721 9496 3364 9489 1710 9390 2546 9309 -401 9252 1117 9155 -1783 9123 -121 9069 -2851 9023 -2469 8959 -5237 8946 -5059 8895 -8091 8853 -6320 8803 -6891 8765 -4686 8682 -6156 8603 -3841 8582 -4305 8520 -3406 8499 -4189 8442 -3810 8425 -6149 8421 -4331 8347 -6437 8269 -5473 8195 -7636 8129 -5895 8113 -6189 8030 -6030 7986 -6230 7956 -4735 7897 -6347 7875 -5354 7808 -7879 7721 265100 7698 -7879 3721 -5332 2587 -6786 2513 -3959 2426 -6903 2328 -4868 2294 -6607 2204 -5426 2198 -7285 2120 -4424 2101 -7171 2079 -5940 1982 -6294 1897 -3445 1847 -6358 1787 -4195 1714 -4508 1639 -3269 1581 -4327 1576 -3860 1532 -6202 1445 -4845 1404 -6786 1378 -4436 1369 -6101 1339 -4198 1275 -4343 1177 -3223 1120 -4729 1063 -4513 1017 -5394 975 -5004 965 -6010 952 -3388 941 -4439 874 -4136 813 -5482 749 -2849 746 -5517 646 -3025 621 -4470 598 -3835 528 -3944 470 -2833 394 -5611 386 -5082 316 -7547 223 -6468 177 -7359 122 -6791 76 -7667 -10 -6137 -88 -8120 -94 -5224 -105 -5405 -142 -3291 -184 -3855 -828
1 2074
0 10000 3029 9935 16 9852
2 2074
0 10000 3029 9935 16 9852 1902 9780 -75 9718
1 2998
0 10000 1822 9997 1708 9968
3 1916
0 10000 1808 9933 -1062 9878 60 9877 -414 9827 794 9758 462 9667
15 2941
0 10000 538 9931 -2512 9860 -169 9805 -1880 9776 -159 9681 -549 9639 1119 9599 -61 9539 1738 9471 244 9409 2223 9324 -553 9304 2115 9206 1421 9189 2590 9146 1820 9141 2113 9074 -739 9009 1429 8918 685 8890 1036 8847 -948 8779 -605 8712 -1399 8685 -437 8680 -3378 8632 -2250 8609 -3167 8564 -1873 8543 -4679 8453
49 2244
0 10000 1397 9932 69 9860 614 9828 261 9788 1173 9764 543 9715 3398 9650 1178 9612 3260 9566 254 9499 3343 9426 720 9402 891 9302 -1848 9284 484 9240 -95 9223 2307 9137 1444 9048 3818 9047 1180 9016 3401 8928 1607 8886 3165 8822 2143 8782 4221 8691 3396 8684 5755 8641 3007 8591 3654 8525 799 8496 2883 8438 1577 8394 2815 8299 1944 8266 2653 8246 -336 8198 161 8134 -2621 8054 -1404 7955 -2294 7903 -211 7829 -888 7737 2018 7730 -298 7715 315 7702 -2658 7627 -495 7610 -2307 7511 -1086 7468 -1304 7388 1468 7320 1141 7270 1575 7218 -193 7183 2435 7084 2215 6992 4947 6979 4235 6892 4497 6864 3638 6832 4342 6761 2867 6674 2983 6629 2433 6557 4987 6487 4446 6412 6628 6358 4449 6279 7331 6255 4760 6177 7636 6126 7237 6068 10260 6059 10039 5996 11222 5960 9050 5959 11112 5860 9620 5779 10736 5750 8693 5733 10320 5636 9036 5571 9652 5557 8378 5463 11143 5402 10036 5369 10208 5368 8889 5277 11111 5202 8359 5162 9889 5146 6910 5116 8847 5067 7275 5013 8192 4991 7720 4972 9658 4921 7022 4830
22 799
0 10000 491 9954 -814 9924 1910 9879 1758 9817 3600 9762 514 9664 1598 9653 1188 9645 2953 9562 2779 9533 3850 9455 3661 9415 5669 9321 4313 9302 5128 9294 2791 9240 4007 9163 1799 9105 3201 9032 2860 9031 3485 9009 1578 9007 2105 8915 -306 8904 2772 8884 -204 8820 301 8760 -2434 8722 518 8656 -2303 8625 -1693 8616 -3685 8518 -2472 8517 -5239 8494 -4118 8421 -6299 8406 -5441 8334 -6658 8247 -4638 8210 -5863 8204 -4974 8107 -7763 8019 -4725 8003 -7109 7974
27 559
0 10000 2448 9993 2126 9921 4461 9884 1582 9805 4208 9777 2987 9759 5634 9751 5113 9686 8084 9613 6581 9549 6814 9492 4219 9446 5922 9383 5400 9329 8410 9293 6915 9260 9221 9255 8564 9183 10109 9111 9836 9056 12880 8982 9950 8947 11730 8939 10889 8926 12687 8905 10483 8872 12609 8821 11410 8815 13557 8759 12476 8696 14111 8659 12650 8587 14833 8569 13261 8502 15903 8488 15711 8435 18714 8380 17662 8355 18760 8349 16697 8270 17959 8269 17472 8214 19092 8157 17194 8106 18591 8007 15808 7996 16759 7958 15028 7931 16591 7852 16119 7819 18637 7750 17789 7729 19478 7692 17527 7661
14 2515
0 10000 982 9967 -1321 9868 595 9818 -597 9732 658 9677 -1246 9661 1074 9596 -606 9553 1711 9545 485 9530 3188 9448 2282 9362 5094 9267 4619 9237 6074 9163 4756 9149 4903 9083 2562 9065 4793 9050 3820 8999 4487 8987 2517 8924 3645 8867 2737 8866 2927 8845 -144 8843 271 8796 -2018 8755
45 2811
0 10000 2277 9972 -187 9875 2801 9831 -152 9802 643 9704 -545 9683 534 9591 -291 9503 2474 9439 1126 9416 3124 9320 1298 9305 1682 9277 735 9209 1615 9160 -1243 9135 1567 9085 -1152 9073 -109 9012 -2682 8933 -2244 8866 -3315 8857 -1752 8852 -1870 8768 888 8736 -446 8692 2333 8668 711 8593 2846 8592 1152 8589 2209 8574 910 8474 1494 8422 -1368 8390 1526 8362 803 8330 3797 8241 3489 8207 4708 8194 2439 8166 3519 8120 804 8028 1769 8024 243 7957 1579 7935 -931 7861 887 7851 -1730 7817 -817 7782 -3651 7770 -826 7756 -2032 7708 -1646 7623 -2701 7603 -1808 7534 -2539 7514 -2426 7444 -3721 7382 -815 7357 -1412 7273 357 7184 -400 7091 1118 7032 -954 7023 296 6958 -967 6926 1810 6835 1344 6824 3060 6819 1063 6743 2292 6707 680 6639 3579 6611 2428 6589 3642 6499 2042 6453 2798 6417 2373 6386 3927 6324 2876 6281 4650 6269 4504 6236 4857 6158 4461 6077 6863 6074 5455 5985 7372 5890 4833 5862 7908 5806 5743 5785
12 2028
0 10000 1650 9911 612 9877 1153 9777 -71 9763 608 9721 -1635 9694 1338 9647 -59 9615 1500 9609 795 9583 3528 9579 3189 9537 6177 9514 4084 9496 6010 9474 3291 9411 4595 9387 2976 9304 5045 9255 3975 9234 6590 9215 5435 9165 5768 9101 3142 9100
26 2006
0 10000 189 9942 -587 9906 2223 9898 -453 9823 1392 9760 681 9751 2246 9692 489 9611 1792 9532 1348 9467 4020 9431 1060 9405 1295 9336 -440 9257 2090 9197 1127 9144 4024 9084 2914 9039 5841 9020 4426 8962 6064 8944 4814 8845 5391 8798 4665 8731 6166 8680 4094 8663 4438 8633 3681 8570 3800 8546 2915 8501 5014 8447 2915 8409 4814 8383 2181 8363 4714 8303 2866 8229 3439 8226 1570 8143 4114 8083 1211 8030 3350 7941 890 7853 1246 7792 771 7702 2125 7606 1336 7590 1441 7495 756 7464 1297 7398 -1277 7354 -101 7280 -345 7279
13 2206
0 10000 1698 9910 -219 9885 2408 9840 -603 9809 65 9711 -734 9689 -576 9591 -2649 9564 -1224 9469 -2022 9419 950 9405 -1350 9314 -172 9264 -840 9241 1566 9193 905 9102 2648 9099 1668 9080 4154 9007 2041 8955 3197 8935 2975 8927 3344 8842 3071 8819 3190 8748 2014 8660
4 2976
0 10000 2116 9992 -603 9943 474 9856 15 9757 1508 9687 1318 9628 2224 9534 35 9476
14 2352
0 10000 1832 9963 1213 9919 4261 9881 2666 9782 5155 9767 2337 9759 3748 9682 3372 9666 5455 9649 4407 9589 7397 9535 6321 9479 7542 9415 4708 9318 6719 9262 6188 9215 7632 9169 7444 9079 8068 9007 6878 8916 9211 8896 8378 8848 11213 8843 10120 8835 11672 8768 9752 8676 11820 8611 9328 8592
3 673
0 10000 784 9971 -85 9896 1849 9823 1101 9737 2186 9688 909 9648
36 2923
0 10000 2790 9923 119 9874 1759 9842 440 9797 1956 9727 962 9723 2338 9707 217 9622 1016 9538 -168 9504 1391 9481 711 9463 3099 9425 2859 9403 4965 9328 3810 9241 6193 9170 5791 9096 7990 9054 6716 9046 8157 8955 7397 8912 10156 8813 8883 8724 11486 8651 10087 8575 10467 8499 10150 8452 10278 8372 9275 8279 11078 8268 8609 8240 9423 8232 7105 8163 8044 8152 6554 8069 9207 7992 7559 7990 9555 7912 8564 7853 9346 7833 6530 7823 7051 7741 5003 7666 5687 7591 4022 7574 6364 7529 5013 7444 6931 7353 6398 7330 8703 7263 7981 7207 9063 7127 8921 7038 10149 7026 7191 7007 8442 6945 8027 6865 8852 6789 7861 6695 8713 6643 8490 6592 10486 6563 8298 6558 8861 6505 7584 6473 8797 6376 7454 6354 9388 6273 8104 6258 9419 6199 9120 6133
23 2886
0 10000 528 9932 -553 9900 1251 9872 847 9795 3166 9724 1427 9637 1893 9595 -283 9563 -114 9556 -2852 9525 -1815 9468 -2323 9369 717 9308 466 9283 2643 9281 187 9220 3099 9216 815 9176 1075 9091 259 9013 3146 8973 2659 8954 3270 8862 1947 8818 4840 8817 4484 8794 5108 8728 3413 8649 6394 8563 3631 8484 6389 8415 5838 8373 8200 8273 5425 8215 7259 8189 4550 8103 7648 8032 4805 7940 5849 7879 3570 7835 3784 7798 3352 7727 4003 7656 2774 7632 4125 7572 1880 7499
47 2722
0 10000 1545 9926 311 9840 604 9760 -1392 9679 597 9626 120 9611 2228 9551 924 9541 1508 9525 589 9465 1239 9400 -1765 9342 -1108 9275 -1807 9202 -1457 9103 -3161 9058 -1320 8982 -4349 8930 -1738 8879 -2438 8811 -2193 8739 -4868 8717 -2438 8663 -4763 8607 -3281 8534 -4205 8532 -3088 8486 -5069 8452 -2294 8381 -2770 8300 -1905 8239 -3447 8161 -794 8101 -2856 8075 -1660 8036 -4059 8026 -2569 7948 -5161 7934 -3590 7857 -5019 7835 -3034 7761 -3284 7679 -871 7661 -2969 7566 -646 7494 -1020 7461 -898 7450 -1028 7380 -164 7349 -3069 7320 -1432 7224 -1928 7169 222 7166 -2866 7095 -984 7081 -3165 7025 -2172 6934 -2976 6856 -553 6819 -3154 6782 -1554 6711 -3720 6634 -2794 6621 -3641 6566 -3371 6486 -3989 6405 -1892 6379 -3561 6364 -1739 6356 -2147 6342 -1382 6308 -3751 6306 -697 6233 -1735 6174 -976 6163 -1725 6083 919 5996 -1712 5959 129 5900 -1962 5861 465 5853 -877 5827 -232 5770 -2216 5736 -945 5711 -3308 5704 -1900 5697 -2273 5661 -813 5622 -3281 5538 -3073 5535 -4594 5511 -2328 5447 -3021 5355
0 0

Cases 1-3: Sample input
Cases 4-5: Former sample input
Cases 6-12: 2 Fjord example, variety of bridge lengths
Case 13: boundary case: bridge length = 1
Cases 14-18: Fjords around a circle with varying lengths
Case 19: boundary case: 50 fjords, bridge length = 5000, all fjords used in answer
Case 20: boundary case: 50 fjords, bridge length = 5000, one fjord used in answer
Case 21: boundary case: 50 fjords, bridge length = 5000, two fjords used in answer, one just barely
Cases 22,23: two cases where bridges are needed from the endpoint of the longer side of the fjord
Cases 24-40: random cases