Input: 550
511 781 98 95 582 626 939 556 658 310 48 287 764 774 314 133 583 14 909 297 151 124 179 417 954 779 726 212 893 332 690 496 282 687 423 445 79 598 356 566 268 44 926 707 622 75 708 332 768 235 188 4 658 562 82 827 142 475 654 535 941 527 318 55 305 642 645 707 957 937 297 392 83 15 271 769 474 774 555 555 152 83 953 431 145 249 910 834 103 722 777 656 470 199 683 549 308 63 36 901 775 846 745 90 16 885 337 281 331 600 718 178 687 67 88 480 804 190 950 696 929 119 458 491 371 1 766 813 909 471 887 88 375 849 582 595 575 162 366 928 446 793 159 698 569 745 598 198 453 803 881 60 18 804 265 380 666 877 679 120 88 243 233 645 455 263 701 47 695 227 288 724 286 734 88 508 254 668 694 183 621 605 929 261 453 756 285 460 946 950 208 973 643 156 54 206 95 35 874 596 543 2 890 347 709 519 658 520 152 508 871 673 847 729 3 172 828 56 87 679 554 790 433 909 755 745 205 166 260 642 521 336 556 863 301 673 431 58 54 955 987 784 842 541 110 190 992 723 126 536 526 320 410 217 99 974 62 766 778 613 954 384 530 638 701 763 559 659 787 762 448 957 873 264 538 344 750 377 35 137 339 789 484 549 553 474 454 555 783 806 493 242 550 110 378 88 798 869 538 721 960 311 859 644 430 810 8 511 816 141 795 30 425 98 990 778 684 532 431 1000 259 491 475 868 939 238 862 269 236 539 500 522 318 550 367 850 609 439 726 24 634 790 594 233 717 511 486 49 283 385 74 166 111 339 686 886 5 900 310 357 192 584 117 388 739 589 386 526 942 680 368 677 54 506 857 748 137 731 563 921 528 117 978 577 976 496 764 151 842 600 390 218 341 773 761 284 202 703 263 645 611 580 26 934 906 693 968 827 607 433 833 299 363 42 419 456 354 273 299 969 521 319 419 661 744 646 783 551 209 508 624 820 458 865 715 202 983 189 255 678 449 326 511 458 965 779 816 854 268 621 650 732 180 857 429 400 358 413 845 381 196 194 407 1000 868 302 563 292 478 969 114 434 39 790 312 640 578 388 838 789 360 882 872 165 825 45 797 200 129 968 14 777 625 682 251 185 130 849 456 548 469 400 695 49 596 636 356 382 293 819 309 843 33 247 693 635 682 261 126 798 845 754 947 464 745 301 740 456 600 230 470 988 526 346 245 529 740 290 442 400 308 355 600 405 681 102 703 595 235 591
Output: 1000