input.txt (14000B)
1 46669 36559 2 54117 62675 3 25659 15179 4 18867 82784 5 94354 78485 6 28985 76228 7 42358 34206 8 59950 58682 9 97799 24655 10 52935 64167 11 59303 53728 12 85106 71005 13 50792 91433 14 13407 14222 15 67886 61779 16 16895 63137 17 30061 23324 18 52760 28081 19 58542 49063 20 90229 61487 21 13000 11872 22 75051 16072 23 95703 59610 24 71514 95236 25 38533 15786 26 96889 17973 27 50570 62950 28 22045 76693 29 57193 91433 30 14748 85022 31 10514 38767 32 29334 47840 33 88964 45642 34 48941 39483 35 70592 24655 36 93664 22449 37 96355 69515 38 81294 74800 39 48811 85577 40 45071 85562 41 92092 82630 42 84197 76933 43 97582 13139 44 87792 86408 45 54977 27338 46 99783 29891 47 69620 61216 48 13987 77826 49 99852 96463 50 91433 60831 51 78088 46665 52 72987 42777 53 42868 69997 54 68892 46927 55 34108 66123 56 43478 18458 57 19787 42868 58 94776 47041 59 79484 42868 60 51651 87993 61 24205 29529 62 44859 90283 63 20200 73827 64 87459 73406 65 56046 83755 66 91769 22449 67 67206 27695 68 12181 17936 69 60868 83249 70 38752 22334 71 99845 94472 72 41505 61216 73 60128 24655 74 29568 78485 75 22811 63720 76 58897 73583 77 72379 79339 78 37663 41578 79 79732 61216 80 73155 46563 81 81753 43279 82 51621 51888 83 93416 86408 84 47921 59610 85 80800 23324 86 96164 73406 87 11851 98656 88 23151 90283 89 38856 89669 90 68276 82552 91 98955 32695 92 54728 30695 93 29338 75446 94 62950 59047 95 65523 19589 96 37775 59752 97 44035 55601 98 88679 53778 99 51799 86633 100 88184 62950 101 91162 78485 102 93338 54646 103 88930 17554 104 86160 77826 105 11460 56897 106 25918 45594 107 72148 91433 108 92158 37114 109 93731 49360 110 87043 44224 111 33307 76228 112 28611 70786 113 13314 61216 114 65566 40058 115 20245 63137 116 37773 33408 117 78163 30754 118 63537 76662 119 64165 11339 120 80838 23324 121 51282 29108 122 25277 59610 123 59407 75468 124 67162 32283 125 29618 22449 126 38169 77435 127 74644 65347 128 15925 76228 129 64235 87695 130 14313 31523 131 65574 70278 132 94576 46927 133 28941 76693 134 56933 75648 135 90283 20996 136 15912 76693 137 37371 11483 138 42928 61216 139 20043 15456 140 79060 50351 141 95841 86342 142 90503 22449 143 34098 55194 144 59349 27339 145 52463 49245 146 44382 59610 147 86377 39994 148 77346 51349 149 32396 82630 150 89974 40626 151 56849 67629 152 62875 86860 153 56067 34945 154 92962 49059 155 62901 46892 156 25886 77783 157 21697 96304 158 38147 17270 159 14550 90283 160 13342 70663 161 70611 68152 162 20481 21488 163 28904 58215 164 26634 39518 165 52203 30752 166 66212 78485 167 90182 98936 168 20740 15786 169 66065 65617 170 61202 45164 171 26862 99261 172 58796 40132 173 78079 70988 174 81851 93597 175 71297 91433 176 92854 65509 177 80295 27424 178 63299 44867 179 15813 58215 180 16650 76933 181 53617 23324 182 26984 16067 183 18903 22496 184 45338 10448 185 78888 63137 186 45642 41937 187 33541 24655 188 48364 44977 189 45753 86408 190 38974 87966 191 74367 95952 192 30987 24768 193 69198 61027 194 79165 23324 195 36565 49245 196 93880 23324 197 58577 22449 198 88572 11153 199 23891 35210 200 57919 56916 201 68618 29125 202 69689 24742 203 63792 67434 204 42378 91433 205 30886 85562 206 68874 73316 207 47080 76228 208 17364 50012 209 26523 95236 210 91160 12505 211 82072 63137 212 85218 88792 213 21179 45280 214 83540 22449 215 62790 75446 216 99201 76966 217 24655 91601 218 15468 59236 219 69939 40216 220 26652 51063 221 72139 22449 222 38765 15786 223 37220 73406 224 46720 15786 225 23324 12724 226 28463 22865 227 74495 12866 228 81338 47719 229 48576 67579 230 57908 85562 231 96483 75446 232 12243 46927 233 18922 30274 234 96066 50932 235 32506 57089 236 63137 18017 237 80079 34565 238 78238 57507 239 29990 85562 240 63341 77826 241 53097 89535 242 77250 67346 243 18752 22230 244 84225 91433 245 23056 22728 246 72203 44957 247 12182 95236 248 54287 57853 249 78417 76693 250 79546 61111 251 97938 90283 252 28464 91433 253 43864 61216 254 25327 45949 255 76917 18588 256 88304 61216 257 16599 91970 258 90372 38723 259 78721 47963 260 61712 73406 261 40506 20355 262 80458 13289 263 50334 49245 264 10066 99664 265 33077 90921 266 27603 87695 267 51307 62936 268 18791 49524 269 90086 98799 270 61487 76228 271 80381 77826 272 30353 75446 273 46686 63367 274 67471 50064 275 22404 67635 276 73240 47665 277 38824 85562 278 52873 78957 279 89294 79544 280 55505 36605 281 21363 73406 282 54456 90283 283 26147 51518 284 51044 98236 285 27948 22449 286 28048 76228 287 52852 87695 288 33020 76933 289 66414 51084 290 29109 75446 291 10430 72012 292 53057 63137 293 99531 27252 294 77723 76933 295 87307 24655 296 81886 50012 297 97967 90283 298 24057 64661 299 23205 63137 300 18662 76693 301 89627 25871 302 70743 50012 303 27182 88872 304 75446 50012 305 88535 38500 306 83093 69995 307 67214 88991 308 79553 33819 309 61690 50012 310 76228 98865 311 50955 95236 312 93037 19499 313 24196 49526 314 59691 67094 315 35278 90283 316 61597 23324 317 56941 37523 318 20120 97355 319 87535 87032 320 41203 63891 321 16392 87787 322 72594 75446 323 95236 76693 324 59675 65584 325 68845 90283 326 78485 33285 327 44280 62583 328 98434 19636 329 86408 22449 330 49172 15344 331 33704 41932 332 57434 72228 333 72242 16591 334 55017 75193 335 57538 97837 336 66108 35681 337 22194 32467 338 74204 41085 339 75528 56270 340 55070 13932 341 12362 69548 342 80880 46460 343 92437 86408 344 62756 37768 345 61713 33991 346 65166 15786 347 66265 57948 348 59605 81427 349 95292 61216 350 53322 61216 351 92343 77826 352 57881 43673 353 25694 79166 354 50803 62933 355 12557 76228 356 30235 63137 357 60145 59610 358 69385 54371 359 67591 95236 360 75778 57891 361 32402 72023 362 85763 79371 363 77826 58215 364 54653 52717 365 43427 73406 366 87693 78923 367 42560 99999 368 56662 98907 369 34358 15149 370 72062 87084 371 87457 25270 372 79098 46927 373 96786 63137 374 12893 90634 375 72153 22959 376 79455 13986 377 94850 28046 378 73433 11290 379 18596 58215 380 82630 78485 381 33604 14849 382 15222 74035 383 61085 23906 384 36243 10054 385 61417 39396 386 97586 61216 387 38303 13532 388 46927 78485 389 97158 28915 390 47223 24655 391 71928 16050 392 48850 10274 393 63968 59834 394 74998 51096 395 12237 16089 396 15340 68204 397 28588 86420 398 27774 27427 399 87417 76693 400 68167 20436 401 82772 87695 402 16746 41792 403 49969 76228 404 68165 28891 405 87687 73914 406 31995 73403 407 51948 57812 408 92704 73961 409 44851 23324 410 81688 48766 411 92752 24655 412 87448 42868 413 14258 13555 414 97152 95236 415 16893 58215 416 49941 72107 417 92908 95236 418 30101 75629 419 83485 19453 420 70442 95236 421 90285 24655 422 55498 23539 423 38791 77826 424 51701 84708 425 30330 59334 426 59586 61909 427 69360 16800 428 96194 66338 429 26813 94571 430 16730 60469 431 20452 61216 432 88869 62950 433 36471 85562 434 48094 11994 435 53210 58215 436 25883 55787 437 67454 16997 438 28364 91433 439 29596 18200 440 39653 42554 441 78247 98641 442 68869 10213 443 37243 61575 444 78248 91234 445 86264 24655 446 42101 22449 447 81992 77493 448 65269 73406 449 79512 88490 450 23050 68216 451 71745 32372 452 12275 22311 453 72704 57374 454 40391 37266 455 93996 81448 456 60235 71232 457 23986 45642 458 31562 61893 459 76700 68049 460 95646 70208 461 19567 23324 462 91012 93539 463 29318 15559 464 25010 11836 465 35563 51368 466 54704 76228 467 49819 40935 468 33230 61216 469 79086 14268 470 51170 18475 471 66485 81497 472 18849 62950 473 64392 24655 474 95125 54268 475 57789 27894 476 59448 86408 477 47257 86384 478 15786 91433 479 61948 42868 480 86728 58933 481 99498 59808 482 52830 35210 483 70990 70735 484 67116 15019 485 63821 73107 486 27729 77826 487 61964 32077 488 36375 88334 489 25299 59610 490 86368 55921 491 86423 71213 492 73061 88241 493 98588 25835 494 13938 21656 495 99826 95236 496 37553 68730 497 64667 62007 498 93565 82405 499 42768 29866 500 42731 76693 501 20204 30794 502 71882 28231 503 93933 73406 504 32525 84373 505 89842 64081 506 31297 45009 507 27264 75446 508 93838 64694 509 60747 78485 510 13328 22449 511 40592 95236 512 91398 20009 513 11574 90283 514 96548 35894 515 34268 49890 516 86325 39672 517 63884 15842 518 30812 23567 519 69993 24655 520 22994 85977 521 36141 24655 522 17881 23324 523 87053 12341 524 85897 11252 525 64282 31676 526 83859 82810 527 37811 70856 528 30617 65639 529 12124 82075 530 25279 61216 531 50876 76933 532 93773 75446 533 11066 73504 534 75494 22449 535 10852 22449 536 75214 75446 537 17183 55952 538 40332 91433 539 29117 20899 540 30888 45919 541 73512 32221 542 78708 26250 543 13367 76228 544 92813 97383 545 51110 47725 546 25552 95236 547 31096 38747 548 83451 76754 549 22497 49245 550 42453 76693 551 91372 53487 552 91733 61487 553 71459 79153 554 45515 95236 555 25529 81102 556 21597 73394 557 43122 82630 558 63641 64171 559 77303 61216 560 37944 58215 561 11386 77826 562 77018 79070 563 82992 96114 564 51119 77798 565 73221 23324 566 18732 34798 567 42279 46927 568 89508 73730 569 27791 80194 570 28523 95308 571 27555 12881 572 29648 54618 573 13577 98443 574 56947 76693 575 36475 87505 576 38270 71142 577 84688 28274 578 19271 76693 579 23825 22945 580 95718 51459 581 91764 51788 582 27386 42182 583 18677 55015 584 67612 76693 585 11810 44178 586 87498 75376 587 74359 45642 588 35714 56252 589 86955 70950 590 28543 86408 591 21253 57179 592 81283 73406 593 54208 83349 594 87550 37110 595 88194 76693 596 68969 49473 597 94869 80272 598 18066 64411 599 31310 15786 600 57043 78434 601 55440 89060 602 88510 61216 603 69221 64444 604 45336 23324 605 39240 51320 606 86973 61853 607 78101 71772 608 24917 38491 609 30454 84950 610 95917 89580 611 96914 78485 612 77197 50552 613 67382 31174 614 73864 88832 615 68112 77826 616 34762 15786 617 53167 36945 618 58539 32505 619 67660 41818 620 89709 35248 621 87156 49245 622 98670 84396 623 12340 44671 624 51671 87514 625 47948 18060 626 69823 76228 627 35233 73406 628 52807 24655 629 94057 26388 630 63741 59610 631 82004 66606 632 93513 60231 633 75084 35371 634 10372 88851 635 89866 46927 636 24553 79589 637 20556 15786 638 46412 22449 639 78846 24491 640 98088 76693 641 31170 92173 642 94801 52961 643 51058 13445 644 70594 50037 645 35346 50338 646 78257 23324 647 73406 21744 648 68359 46927 649 41213 55805 650 45250 42131 651 43279 18812 652 69199 15786 653 53725 76497 654 69398 37768 655 11742 73406 656 65219 58877 657 31780 38597 658 46113 90283 659 30112 76693 660 37748 60472 661 12596 58428 662 22346 98357 663 43346 53539 664 89142 78485 665 14544 38869 666 31577 55185 667 55937 87695 668 41189 35667 669 25078 73406 670 59330 94542 671 84733 16627 672 82488 73406 673 82948 58215 674 16789 91433 675 53671 27376 676 70549 50516 677 97581 54013 678 91708 61216 679 64783 37768 680 89911 46097 681 74663 76228 682 70646 60061 683 23944 31181 684 30697 93934 685 27561 95236 686 52655 68084 687 90627 38964 688 27641 35708 689 14184 91433 690 42968 17857 691 72204 30261 692 77368 35970 693 17048 89985 694 20782 18407 695 64749 78485 696 41007 26752 697 11880 97776 698 44202 24368 699 97301 23407 700 61077 74465 701 38804 77826 702 13897 48877 703 14508 37578 704 61383 53091 705 16885 29289 706 37225 52081 707 64685 35992 708 31682 95236 709 63631 10368 710 45781 24466 711 24092 65388 712 31728 76228 713 45777 22113 714 51779 60657 715 33859 29358 716 53484 78827 717 61319 49899 718 36093 48789 719 40584 77905 720 56381 54295 721 22662 38614 722 24641 22449 723 88324 59610 724 78924 95236 725 74820 61487 726 77398 60846 727 99595 63137 728 65832 49245 729 89471 11285 730 90188 76593 731 97763 71720 732 98824 77826 733 14418 20513 734 39862 73406 735 55906 78485 736 86059 29127 737 20742 97241 738 88269 91433 739 17962 86920 740 32602 49245 741 95412 59994 742 83267 70431 743 36825 24655 744 89562 43279 745 16860 72596 746 53577 96790 747 46665 76574 748 71813 67270 749 35210 15445 750 33400 76693 751 96069 65213 752 46322 39179 753 95285 91433 754 95767 86269 755 15236 76933 756 27778 49357 757 16170 30140 758 57870 63137 759 80794 63137 760 84281 57089 761 91022 26553 762 55848 49245 763 13825 49245 764 91230 87028 765 54860 73406 766 66596 53306 767 61216 64519 768 50012 76693 769 36465 83257 770 87188 75446 771 73588 21801 772 94757 20402 773 28170 60768 774 24891 38174 775 91787 76693 776 63785 43279 777 14566 90752 778 55392 90283 779 39790 67787 780 40079 80845 781 33827 34045 782 79864 78485 783 82775 43279 784 67159 10612 785 53001 37768 786 52173 58727 787 28322 76933 788 84518 33044 789 76693 27243 790 49225 44682 791 22449 75446 792 80658 49373 793 43255 22449 794 59058 73490 795 44951 49402 796 71201 28356 797 55944 42868 798 33202 83266 799 86699 66983 800 88453 85814 801 77034 58838 802 85850 76228 803 41409 88724 804 36649 11112 805 88428 93089 806 59610 66639 807 48137 90283 808 86400 90487 809 28104 46927 810 43317 59610 811 85510 67445 812 99532 78485 813 70359 15786 814 42034 88131 815 80957 68660 816 43032 95236 817 33582 40382 818 58215 94486 819 19221 36076 820 91307 77826 821 64821 76693 822 89517 63137 823 53579 18009 824 82987 91433 825 94727 51659 826 19906 91433 827 80106 43532 828 28240 71843 829 29670 23324 830 39700 87695 831 47283 78485 832 39801 76933 833 25980 96028 834 21945 71497 835 78407 78485 836 85640 45318 837 51978 50012 838 11601 76575 839 83651 31125 840 95958 95956 841 77749 23336 842 13537 84975 843 88065 52971 844 38210 98657 845 40101 36035 846 32397 75288 847 96618 16256 848 42989 19324 849 72932 43609 850 18771 34539 851 58557 86408 852 92319 79573 853 38295 94964 854 10485 63913 855 31358 76228 856 38846 75446 857 72221 22449 858 66323 76933 859 57089 60456 860 88674 50047 861 75813 15508 862 22055 60704 863 69047 96120 864 73862 15909 865 83222 67849 866 76393 80920 867 76522 69689 868 71666 76228 869 63583 12283 870 19328 28164 871 39355 77826 872 85096 76933 873 42056 31488 874 92747 13579 875 84937 47182 876 17024 82132 877 56871 90283 878 97790 46927 879 22993 68190 880 68482 55096 881 79976 85107 882 90940 52882 883 65919 63137 884 62007 49245 885 13415 59610 886 26893 24655 887 44653 95236 888 33612 99036 889 46478 42868 890 70970 80135 891 60481 95236 892 15301 59360 893 17212 37414 894 80899 75446 895 67495 21742 896 18319 14479 897 34445 58215 898 39486 42282 899 36028 44519 900 92208 46483 901 88362 90245 902 53764 48959 903 85604 74027 904 96035 95893 905 29561 30742 906 74152 61216 907 49507 46274 908 87695 76693 909 18100 15786 910 21313 73406 911 62234 12938 912 25025 49466 913 60890 74332 914 11565 33629 915 84299 76228 916 34861 90283 917 21353 73528 918 99978 66897 919 46529 22449 920 13104 25219 921 68752 88910 922 26478 76933 923 87668 43279 924 49777 25060 925 86763 75446 926 73023 45052 927 72004 51554 928 88141 23926 929 33130 82630 930 82472 22449 931 64754 80502 932 57842 62007 933 93088 72374 934 45727 93735 935 53996 19768 936 49245 46046 937 85299 19540 938 56446 63137 939 92445 82605 940 67790 75139 941 16758 26579 942 66664 89655 943 32710 80610 944 75707 49245 945 65814 95623 946 58220 87669 947 16612 76228 948 24698 16590 949 23184 73406 950 91238 15786 951 11843 91433 952 86625 85562 953 41307 77826 954 26670 69594 955 64855 63137 956 63544 83733 957 56574 24108 958 79163 67158 959 99311 95420 960 17640 85562 961 66865 91397 962 31429 37768 963 85562 49245 964 93263 76716 965 81248 45189 966 91852 47062 967 58324 52943 968 63446 36264 969 96407 87488 970 46436 57089 971 12385 26581 972 91195 25257 973 88835 32326 974 21315 77826 975 24216 97211 976 37075 50012 977 46375 49245 978 68824 88237 979 24882 44857 980 60941 75157 981 61864 64400 982 41858 97465 983 83877 61487 984 26722 85343 985 52455 55804 986 22568 74046 987 93290 83623 988 76933 73008 989 61124 76228 990 32025 67436 991 26293 77826 992 46658 78485 993 12043 52527 994 47464 24655 995 56275 41945 996 57840 33284 997 60040 82705 998 10256 95591 999 49049 90283 1000 37768 43279