CT30407

The Frugal Pairs at Tidewater

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Jeweler found an old ledger of windows in the aviary attic at the coastal hub of Tidewater. The margin notes pose a precise question. Task: Print the number of index pairs (i,j), i<j, with a[i]+a[j] <= k. Input format: First line: n and k. Second line: n integers. Output format: Print the pair count (fits 64-bit). Constraints: 2 <= n <= 3490; -1000000 <= a[i],k <= 1000000000.

Example 1:

Input: 3409 1430337494 919387169 504916157 617164325 16703657 81133907 354753134 552557550 983871229 887357017 663265646 221638259 923555324 131535432 844040353 984657192 662963708 836198794 196990940 552780335 47648148 160526639 390119489 136753492 164127474 55725627 538569135 907661113 41857949 220907392 976979096 960274619 472841355 33429060 580703002 38168460 474072024 992415805 606595281 911964852 317705269 986926464 841213441 851204388 127273125 688597549 105459019 508985111 271571442 614571521 790268847 237297276 537768852 445828817 41735179 914684539 712705949 900301355 324245089 253949591 453289114 534497781 222605740 533129375 539165617 88870164 310448339 791554346 910341939 886075017 885029661 290075947 95368818 702957033 926214970 406000045 68523354 424029535 848258978 268351008 443823396 666011562 612264852 857364497 661193097 97044021 489051179 710665209 545851981 254900335 638286289 237880877 745017916 904820107 427043534 91203843 277415528 821028761 692648123 926613391 243256889 425677413 943147586 924830311 393365147 42890070 802907901 262167029 662288202 405555190 903606118 326728085 823434960 842073597 534656080 529934244 388081844 642916937 831912889 13659546 520271246 897254137 454435807 529845633 784102221 587076533 497218912 95143976 889154519 452588915 794156674 204234187 486699904 209878754 395972570 593565434 73996566 823492316 578477035 713240689 87542225 892780214 17242775 183273432 919829146 228343657 5421413 860395186 276863745 92834918 659138145 722532983 570135229 296479542 529938540 822414352 37317141 710106688 663922094 836053637 289777128 496599980 31866339 492385952 487602249 523818786 75361973 531947814 583847638 257536529 573494544 670848344 640796109 601546027 36276128 209637542 332547362 672235032 346684346 779535343 98267539 245601549 340689439 650081359 444659724 788329581 893502119 221949640 296060415 622249712 210358913 389742962 929672757 431304129 64488865 867868128 502507737 10634592 467674858 644073898 43873733 848695155 165090764 387780995 616685255 772222658 315226602 534208867 567733933 872152091 77542460 494790745 962559081 621557252 931478010 524428575 652435651 340763774 470531911 324877564 630842204 269991336 365624467 509928199 122282240 771079189 394168596 7691708 762754895 697840686 818587003 956231976 255913088 380212990 901447666 832252299 348373981 968077418 714080250 909937198 417742919 146329883 172077516 560705647 174805408 30488636 934446787 442008697 109118345 787508147 928278858 401982462 90457641 861138634 591962416 720167322 417889880 871967253 967061535 56199983 589023585 809003366 333820827 154964692 442166153 766953129 208051021 22131858 715561207 706213045 739548001 383773143 368751551 727770407 480385017 790366989 894690989 141634053 151472125 266743874 760570528 879867259 122399320 460856384 32771474 858033095 665520724 79011187 26421788 18226023 569414937 894895477 462992844 120956744 727793996 547591965 700464680 590718471 473812388 228509401 193861528 938405653 553649605 52683769 204888349 430196999 195150890 465831807 64549792 757083480 490940011 257528103 703009501 68052764 190989149 601776147 576900090 845115602 133678490 257265928 667809905 770003138 310135327 383951561 118497696 933712284 523982427 428070951 611173530 467756147 761631670 975449540 862368120 496392331 322285010 452282715 127009440 147426557 176878519 80047184 559477491 426760567 274416617 422562123 528595186 12013239 455260954 579629951 985796310 116973124 340043195 430189090 617155201 375724735 909028899 109351283 33925540 822411585 692399942 973615000 445408635 583154941 203781890 753215630 897204047 59562181 771209483 700411410 130815912 262714709 33741827 595305606 244848034 645287388 533513743 354839215 864236426 267880787 665569596 909078413 935329638 636795992 897824982 754931599 920952679 621173830 312378923 123694007 297677995 851442534 956014170 357734379 765735701 923917340 33238889 186328517 140021556 726789690 359138992 843298880 520891036 79157843 982266125 515535957 406319410 640002647 328075649 224479192 220813078 399345070 47218741 739353427 847580377 232666980 662613324 586813777 727772055 964828238 167585937 659196250 668483527 158712265 70043271 751472808 904939691 86385378 429280269 246885947 201007030 980398319 256110510 742786760 26430724 784039197 121287213 567855740 378273518 239590101 841591498 513554852 643118301 577225339 440562031 820104160 614680416 371469095 532529031 444615713 340864325 266826156 16079724 494222745 621568771 843951092 864193782 626956993 366191885 799011461 49458971 178129384 617169258 561605365 398892655 12727177 901179434 802115524 704569717 700566906 111797390 21422775 200122771 225739791 509150142 461065989 362913435 663974309 158657613 981440309 809640691 727533178 115829289 453857281 604508794 552094258 120080798 375397678 739736492 539437189 275173142 20401023 48929334 707532127 137993013 624269232 466811983 820936629 665992327 626170455 654316002 14891923 939302420 883865978 713761412 651988169 994560793 256524852 459823169 412828720 283924187 350419669 515391532 334438234 354711011 290679446 374853098 810984393 887020310 200163585 771228492 282222331 982209357 747174499 992423064 903331569 757286537 869295227 30420238 722883160 938334091 664561061 794328029 548664455 972433294 368037532 622561273 210289870 33248868 314385773 395482651 359898177 703385652 370219462 43337941 44997619 521962064 914679600 512979987 694423627 469801238 32635277 431800106 544392190 451773263 44986124 592833962 164011175 526349691 619025639 755503364 298694627 596615183 83197799 927708840 830273596 11887402 503404848 77662919 299197979 532445690 157359440 229284691 483749501 941493163 375237179 495962463 718963795 605628634 338470091 147448040 533316904 22118379 221332060 197897805 694507656 252835318 296597706 844463509 737674649 645429879 578811827 396459641 294974590 730751934 347569138 345196210 709643068 526017021 195137649 459386655 673843743 520966868 647226912 331358048 198430184 849991341 740795103 811866273 366975324 52320307 224000294 875677544 185282286 559125100 166467282 651376968 423438933 637775165 520661112 689840526 577813459 975221930 538747075 632002658 166046833 568120120 685564277 94114675 285774644 331999599 706721825 83342174 589173190 323690344 186779692 32040864 673551029 395141666 547756049 766643014 639566291 409720706 335162921 279364898 211132358 100674104 64767369 102241032 98371659 498667224 462757012 105129034 649628884 525215280 180358788 803549034 928056339 979303881 221759630 275069575 241881952 830180727 510713831 28700827 919597518 64477697 448930491 410213737 390872345 313468482 50337402 625810043 923777778 281941759 525122917 640480678 785275615 457138609 405583609 122769185 693953716 831585585 403426665 77953442 269605830 160397591 222734158 914040186 935204174 168969224 892843546 576346822 837367221 93050553 769193441 10467211 949394063 394371518 81179255 12960829 667767730 429119261 756189230 957648125 293374530 671900849 479691561 384749762 293398024 421554047 768063349 946834337 272935430 755682958 452231369 292273139 805533726 497423769 246912470 599671508 986197150 208643233 43192309 399782374 143184716 425237282 172266162 234773942 212772659 862831409 1656080 768162542 234895975 982993039 350550443 528652336 797335050 583559983 750781339 927981246 490115883 290427650 987639484 804561314 846678424 323687612 928285466 188728301 389638596 418102182 424647265 258851688 547895992 692996989 984360012 110831262 122825312 852404174 631616376 901679406 313407937 180425448 837500531 291204995 775163515 592898734 744527866 375860556 690325120 476746326 778425795 115666782 753857624 76113217 184840544 317638794 194049949 753450791 311172883 540594456 775008004 533705334 855269933 231830812 576107677 594954329 350215080 391784854 946700866 907124853 966734051 229153130 627504333 627563439 811664616 857486871 455030921 760402054 618403583 290517743 205704599 80558542 631650921 555227873 771318188 145789985 5079275 786821077 871265449 627578891 371288221 91380051 246207473 476614076 182502885 876278681 489108522 477958559 604690885 208503554 801957425 871954936 858887318 578473450 156214056 415712653 208579850 3268336 710378106 701101083 868987513 553340859 900951444 369170527 283320217 82019046 353002209 420617887 706049745 15871060 598871515 432544871 145064997 737046930 267401968 327664176 137889811 286281679 594757001 943845621 85387741 685893811 112865695 579635330 504446100 433970283 30615065 568173484 390446106 798139303 600079108 912544469 398804994 473254941 901917263 134755583 206151230 623289799 241149258 372980871 812990225 71627255 198039212 195670337 995868967 186590601 140861750 597970115 186090209 12189169 268403410 412681757 628271546 552062747 831734522 563541950 126900637 382732967 219494602 894938023 39043448 247504000 933735043 160719732 739995252 245617774 689575020 865260044 814245560 416252290 695244863 495659716 497421872 492546983 253143958 615249694 445691268 721994514 487195758 427375789 298070486 672906329 123311742 263202537 653655137 286138210 137374878 645311608 566805175 89996189 605010165 801084294 375244653 470810458 59846208 770915727 852433766 518139496 630752644 760361630 285985256 363972197 114002249 374303115 982081021 471636389 825714321 774022971 624053105 664082053 651294144 560813422 900441478 552915385 437549688 60231898 313164120 383447846 497870532 595882154 644265103 790378671 156628272 783488086 427010194 194224290 251375671 574612439 757913241 784194944 356905948 241172308 323273958 126557699 473608175 179223652 301092577 912070733 399304540 542889603 797187349 871415491 303503951 285803940 60915128 52988376 306256165 399856941 318528977 750225157 89154194 800430573 344979673 703649846 34671692 165116617 95479735 129794822 516226525 416126319 193394754 529756704 931823420 223635447 779587631 466405774 399007197 689678317 718075891 195943162 684510991 682780666 887295549 572088331 884757151 212454504 485167262 600191157 432308158 700237240 274868761 453792292 983699735 592689211 56530322 548995095 830536934 772002108 31323330 825635540 189360451 894290199 319709846 661771619 3539882 665733118 155534783 551687944 5390507 466156135 51578147 978307076 612794146 958183245 995241252 802787770 935130321 862884153 865093512 795640869 38985399 383989125 333418179 724987697 930724138 476010611 497032571 193344703 708438230 367029822 833486771 676739781 860480601 465578343 479229631 739173923 886985622 688310586 57850460 629835978 762352395 708794205 22493003 490731651 859702101 964122070 91654877 170629623 754637187 651774605 716316730 251766679 574019608 942318241 128870517 516620028 393180985 572469402 952759602 829165104 264737735 753687629 438377473 671591318 381854676 204058148 633184605 327659631 629240350 306432399 476766141 438691821 703755672 586326453 731799766 392338139 287973603 178260554 680397756 922383855 985067631 880882852 851175252 367898045 278221776 878940766 624584475 126235279 726395720 727561475 802106617 804913532 816262289 287341185 42126419 186459626 594435532 253743661 974891491 317528193 801325787 637762110 888566448 309882338 899374725 32836978 307835030 605834723 196117108 334403632 371518826 148735250 835448361 491261012 711676240 961624731 949570982 745985484 77508756 282942270 456807565 386185643 566371784 449804057 520072792 687022723 192780585 861142312 465486967 729777645 763050670 276604182 16487683 813828969 393924327 488129378 115066770 448511649 737755764 51084538 459915190 477176433 28907195 787640835 52515262 308697319 838885278 673397747 932640735 399165744 231336754 72617790 325589331 682746908 964008905 345236813 755490745 506816397 189788247 11124386 893879232 590517132 413650194 757579231 708998143 901615841 554066186 160333385 601669532 839532783 721482009 892249269 984661831 365656616 253777576 548885847 312956064 491326894 611130317 985597463 953648879 344956601 580137389 339137503 815762538 320725294 39852533 707963614 101380237 412182925 449256721 122290953 522794086 141576333 175408981 689072070 101396280 865440164 228559220 917283925 629105583 302405653 136823947 290583912 474509502 277033162 698514738 939299044 4170429 775839515 637137625 255216432 396135258 844859137 695280878 415051151 804225164 497611254 296412549 107720207 427015892 234301177 814799736 627482887 688664398 107012024 775109393 693148738 489736202 738506949 31068292 519318362 721621580 476214295 653662669 328008395 923727259 147028038 393394020 410751009 99789568 396277610 130851177 293472084 574089874 118260375 202855439 595436016 478859180 927451293 491787409 291034681 969430015 117627798 320344025 479509759 455097569 141143647 500605247 943410385 214790788 281714573 333502882 361409576 339917983 146018586 863159920 357045776 28675498 271970839 751081953 114083369 104483279 565972879 94686117 958750980 162842193 194954542 659566105 300009378 315968924 732632177 972874926 242239852 901571912 432977941 921208703 13892769 718601529 608104821 811531351 615410747 803590131 426338927 828277734 43417790 299346185 172018364 634500089 366182300 164703858 106758289 432459245 800661688 547423479 271508873 889948196 282322952 320160926 524333128 541135626 814833297 285840314 280735514 772501063 851131902 271818218 446412636 530505218 54039996 979399672 608185764 368234785 768065544 564174620 511003305 183084401 569520058 952851259 751086285 893940273 777174895 656799240 882453021 692742365 792444458 455731567 860347336 -779414 902613589 307550817 476371269 7269251 260222148 831792860 773864714 72583393 153212195 646788295 467901653 104091752 721775752 339439023 169099042 499572536 309472877 333040682 911582849 676768888 624867238 131679883 762167400 615303686 182223804 101112264 756761543 194743770 574833866 298461818 55989721 811242833 201460150 468213257 430513225 363438160 166096213 148540383 383413991 600047257 506049216 238943101 73327685 503410384 341344604 380964685 317162007 49336122 695033048 390655071 886341481 369927204 17794453 969188737 341419992 556165533 606643231 740845050 238663441 3368643 938768026 436357876 114053097 106262347 172701295 323761416 595922141 81853231 -741722 934308366 169931111 907414223 311775367 303506928 522607136 379528019 168235235 712175563 942443546 620636273 161088708 679421359 363198931 914669685 123952801 365561986 807587908 75726185 860135665 498988777 538087588 25376931 565703388 156030675 572555925 666647730 144192967 190422673 461803752 266280334 251028604 539873863 623865357 344103140 80927333 895402606 25063516 900006303 708602977 854392235 380958316 201305284 277029203 566412361 837175687 813915005 23935868 735985557 845653298 533180043 425465710 970343766 890533235 901259475 226215656 97050188 110682099 242763813 926330771 431736449 820991654 975921153 188040938 878282055 101030613 662312077 718337478 814883587 823858512 464070477 85541786 341176880 276798871 991202407 939689220 820273166 803177266 494933251 291114850 722677476 399858722 816537766 939171711 157244300 695523210 541241069 796357313 918517311 97423741 713248619 418825140 828721564 751696657 746969922 987101613 971735657 872885968 258697197 652978760 720979222 154298857 17402329 724711398 635595713 848299018 357094907 110897600 876959914 74631941 718956909 421921394 501656084 357208739 64638184 411836955 285454138 768409044 640901753 297944640 733395943 719698372 961840245 64475262 157182701 11756571 594479569 883221306 108371730 114835269 293139071 758893237 272174919 289527171 726041949 478598367 305640649 138444297 753760550 408665000 525289871 518860417 991554701 361062448 444129926 555898980 253411437 143928383 625938555 489962812 251593454 920228506 193264143 420327439 869845991 655569098 155075503 942613309 410646213 603814642 986208645 50921194 29714363 582632928 446440235 694556469 818160520 44289965 723058941 406303773 227214832 832183063 890622613 967278687 976954948 163840036 294478400 114899507 277479666 782472121 29207621 384412809 326717165 679161748 402410415 955660069 760498496 454990935 420265569 262889264 742674458 18651860 769609038 323927340 142682696 647413129 85696494 548251068 316373299 931319434 843093129 66834224 877955035 443497745 392598441 73780425 732787678 821764450 569156544 764865486 324307194 167756101 737416748 215616252 76586835 455666679 924389888 69099363 979524859 613038576 955463737 148036145 975146958 391499953 551149261 114809899 225380452 384787688 619127082 56252791 921836119 612542932 830698832 282546889 933124382 226607940 319836940 396085078 449902640 400994807 645783879 173437022 737086119 612382028 738428989 883639531 976412016 222522180 975003492 144843940 221433315 910206147 551673894 744801991 571095814 4704807 731923349 227091420 822270983 452523863 509083212 295768778 996454147 106536456 624438085 5419729 356139448 939664172 150943843 533319926 645190717 387003562 800986985 76379277 593065366 193936119 567736366 628457469 496610984 31241948 980989746 810464083 929538093 236874219 673398994 891841084 603770109 571214494 827525598 147393086 555590045 887659687 582219225 738409690 766083506 804890653 288623693 155123966 295979099 322087109 809790860 602602857 873424985 425947371 691791762 921446526 859173062 392739801 633594969 154302504 456593934 311854540 310486260 76312458 875186186 151852167 846179936 635686729 604296673 702365213 602805396 565693989 241494479 279506050 21784391 394702323 600569246 538133273 616894625 582434461 183875368 82840612 343219771 768631427 522250346 53188426 776810087 237772193 639792832 783940347 170448799 806525561 858308669 361955693 730670917 136756795 220343080 240071876 894871597 222328251 915005223 346521254 742087391 262525989 557824858 741096731 150388102 906247589 441307050 713751302 626154895 428888827 946428109 833727947 183161486 631766050 277256869 956599824 912946893 569511423 667376822 721671871 859553937 815465982 556080462 573350533 346754531 982728040 86110403 473685882 632061410 821625352 138001166 620039485 360743386 375444866 498239116 943864598 62396223 216542840 907007258 34119588 533384397 646671183 486162934 966545024 733042324 139376382 938057778 558761956 131446106 581168925 901788157 649632923 414577829 241776788 807956807 703030708 111273123 463861943 556037150 649384799 798113645 91733310 847065135 555966041 40983576 961725279 560191652 766259320 396048107 862315596 23882249 460012896 4416073 526144968 785362205 883633514 653278954 834254242 446263838 574757470 796765683 176776625 500743488 83324168 388680836 266918792 127300110 395079660 971527489 444343396 866728333 908088315 165210865 864093456 359018720 444284023 530844216 116162182 569498132 658092942 497928859 979419800 803550633 860678554 917248882 722342229 705228698 74517208 278741742 187395252 754676911 966347544 914554874 735115441 120271656 334213728 222997268 74891883 492154 378725707 94491805 490677120 37197190 879244983 535634100 867717027 747290783 800289213 566073618 484591408 484808569 234682173 248484511 126731407 894288970 782108989 199665470 352300169 746281859 313076817 146597008 612209841 899416805 313586260 805315798 787911376 815789468 280491267 461133560 93998327 216405970 22739183 82445426 511004403 759390682 299044089 259672841 28367097 744490067 457845001 819296901 236837728 383375439 611621047 875108954 501235762 701748040 854877939 19767618 792502831 647472584 234739509 315162144 606382212 644862013 572393310 479174712 992511026 527425831 817762161 491945518 538241183 340011466 555028617 597611681 825760183 90430835 746558181 58750226 710529980 995380023 136903444 21426319 218595125 710513475 449776783 368699281 204469476 165607362 732343822 718885529 478104679 155088089 997604071 618255999 155740501 877566316 662392055 980685978 278980574 494587236 674306216 590499566 87949995 360941903 448126243 263529944 732583959 206508422 223124651 663809416 927507311 795031070 465394731 613960616 702071321 450461669 620126170 444302477 954635560 272525371 639745546 3395361 946418858 871402008 901621112 176252275 722599404 17110353 45128409 6878180 484032910 136762996 191933118 392362757 831881300 64388157 492438 736387101 989533755 348617605 855010057 697198002 906121495 535553017 507887221 969900556 210747681 774534857 534250077 877294040 301361801 252055295 913159739 137054794 219923101 614548653 680010561 39167645 845843919 978937651 988809012 700268475 502920133 557227738 207819606 143068238 216058993 455297637 142875131 567593064 314832019 863926786 122147698 201084807 113458339 272166794 339127740 695659261 334818336 728888247 596914304 900429249 750061383 274974038 979365879 22532535 109036803 82315271 377316042 770810705 211982799 365420521 403452089 751010045 331445645 485972248 412370432 138246770 104502419 220790444 188790400 881943170 761812379 228523692 120682188 -427749 328895916 648516895 498387095 35368610 929789275 410553191 401780287 391148547 612332396 2331953 177367049 920579688 890808755 689001080 611896948 682485351 866243120 447394037 636176778 595150027 588988659 635738793 724947562 643982894 843263064 157822634 582056039 55341953 280478676 723223864 657862171 831887642 460804804 689914762 45923556 37186897 199671767 657012994 770038214 976885270 209389520 852614862 129139454 314896336 898975125 813107259 136785312 576587359 318018131 757531696 453977941 342452457 909471501 64461133 798841778 91190796 970029639 522157862 880176023 929786681 560288976 209072025 166940917 212698535 827379325 143265330 847946690 863881302 930524228 723427727 279080542 953855725 814198776 725580439 180714253 561624796 881130589 110925957 903886418 433214295 396910224 721428681 274185837 376652417 577393628 740326888 949092023 544477279 197380932 896136148 533811448 861769223 406019818 422790213 245302207 613230529 190138321 559761789 404895587 952487161 344736990 744453865 321621203 907695518 658883940 767153188 640313636 784487869 536542279 580609226 561182723 690029586 599695863 513608930 458463023 543199009 668915734 835687628 862565806 215960155 626113841 286736097 194182557 233721334 313341696 923629572 822359859 106939075 383822570 282065532 808150637 543697968 521666980 348535115 243010789 832592500 373800231 523485189 768012549 782926953 926693756 735735841 744091423 76148544 875761507 76185457 812395743 736303319 284301832 773884667 492062018 426113265 492244063 865801328 496889735 846978225 444404194 387539024 302829627 23450678 867439916 43959154 445524475 188074821 893872128 413647177 618523331 211834171 86040797 834770239 147979206 920091935 298843233 964651416 915068886 60376186 351686660 423033910 344438450 936566003 359414293 27315693 365811793 324915192 790730732 213258329 344861768 375848786 94292530 788325742 829689194 491131380 17042055 443446726 5073172 397511379 41009800 971818530 848253671 682604906 649809429 748212726 292151168 328606258 60850645 325339849 74676353 216625858 603827690 757283643 578836535 506524623 758050543 228776240 473858715 594718206 151282400 836533347 839525086 554593653 186867783 675394065 38519793 344531697 399043857 914423854 87412808 195250199 105565835 24496014 565949489 714376036 255946414 970887805 957191252 701890748 892063117 777598514 705798487 798727080 341613434 1680445 456453784 733986290 492120894 287946810 127899305 759534513 461227613 243232323 24981238 911433183 954053022 297973425 328302346 421774106 999172485 109174183 730610958 669768056 741512817 277777252 192091942 535387179 420787953 382770698 909558309 57870118 399908472 886772791 951711067 13858040 932552153 948405527 528938269 491728728 286162410 586028955 249060734 787119524 493185289 145754844 642455732 197876445 219360878 537181051 75158026 923662955 860801695 309602933 496825946 775899493 253952 3889257 928624204 931513531 651744314 99090392 137676779 516145954 51380463 62648606 622018086 826329585 335224449 555199909 67344341 566066091 443952714 321007209 274306513 701780256 497134189 977022635 780110626 751809016 746160314 271685246 577376516 38711806 988111219 69606262 125881913 963109714 674611159 101800049 518628317 916739676 961511007 247746884 266081807 856198988 9082113 274327500 103211257 520650832 161386169 718454200 3730073 31872675 411080439 179978951 731413053 501476428 518362126 488689110 883440564 211114719 558187138 261741267 101062597 940935379 792009803 266716604 757120894 588915588 292418114 865841796 524592489 918170381 167046946 413964298 560565220 807183184 271103193 15881984 438679945 528562771 542911333 247358155 146108242 902153368 421285423 501702731 892436106 218889473 434239732 308394115 705258141 545136564 121949275 34032689 180226828 299709172 779717124 796065703 127516621 682694012 636889306 443275021 433063374 94562849 555081402 821502173 679364365 262264877 386800009 533756397 981618285 149085980 199832232 742905675 566786712 453144485 150729723 893875840 710587000 316696609 546033616 936616479 643522776 435045729 416140805 976744235 159030853 752490735 439207094 249972922 193595184 852044606 300554067 178335238 509207810 78661223 390347534 790796265 885106918 367619970 954893548 809498671 327178607 373061071 351302351 817425966 208217149 129711878 336627722 133454615 813498394 946447707 551458827 538265677 630861724 566128237 902378654 640243239 351945027 971566718 93610231 886612491 118961750 695358832 330133122 530220224 828180880 704084032 531559666 3805918 487035398 619521235 534487583 450961585 791452033 117782560 774202633 29499953 202083633 572580358 981537500 761098240 824094163 776750268 556084279 325960122 646233430 562217097 50216554 345408210 114586726 396113566 833869106 564626871 350004929 965724054 812454308 483222824 240532357 613968241 505904115 1694186 638676019 300618812 365083510 348641047 137299667 192146210 749224551 616892550 187818759 786131474 127912216 312652432 656607276 432352953 176512537 549560298 517460339 397960682 594090134 313095534 242316560 713766202 300493526 830318921 78954561 604033742 186755802 219194121 920215466 511025485 699936717 443869130 66609856 157026979 611718513 487759333 160697711 4179291 299799162 572856236 77984610 950082900 410859125 694981078 561054849 215424899 805188121 36440180 800140707 991559480 26545886 390648624 470598906 205171552 737869867 464900839 621113102 268155700 619677753 307359589 378335004 496744846 896545345 731763794 248377968 709730391 207110971 172676665 907736322 579901553 306400360 997146483 584993725 727217059 535671840 272908685 631747136 831380648 39256451 817962023 370984555 496990178 554745160 896584499 743586223 8218760 111150992 630363245 791605176 674322356 558274982 173011902 396495590 46051199 514573485 471133277 902303518 894215724 5513082 433837568 341759342 464562392 130901714 701121471 774197579 647559400 110686341 836134424 277100447 915776088 420551611 347227447 890607180 363548057 213924029 380246281 581769899 591798649 256168576 301413753 174183040 829548017 245227783 310984191 820106650 462772647 736685962 104630505 457550556 641800406 966461422 726316961 547151375 466546811 990508367 756040828 725744038 522397613 656684073 672609786 312460958 580519832 156409985 362663414 683194226 568481488 740159087 423815476 872005526 621223654 311711543 146795837 798573855 588420745 167863774 776892743 263523428 539294443 55976263 200500459 909758304 809633817 263815327 668740913 682540412 405045874 970042547 932481056 976557879 642859944 381730311 691383253 159141669 760472815 217971362 884637095 660588652 298463716 264750011 282186273 619443274 998087357 753898184 260661709 550648281 927839639 985500553 598885045 737891893 995685982 481917316 382235429 95230257 221749319 642471574 338823558 911076197 882410201 9259593 851247718 958318066 278375222 248228541 834740858 960109877 546109434 76124764 663698522 723849285 946366763 963419909 866015244 446136536 399466853 855423357 453947437 890949870 842740487 228584532 344627999 532355262 890407095 835672488 897595998 516216023 337323538 500786012 414937939 819229285 688013271 694924509 462826104 798192218 493310330 453290786 794183964 761084192 557861740 748926149 275041428 364070303 607092758 306847424 676194867 107015184 744993703 771414588 124469766 638621237 221126833 768089238 869705478 82778903 552557661 220730678 833074749 36228100 906006901 138109330 747771121 264690848 199423366 84512627 952092430 514521645 300451411 621087902 22025920 165666212 342991048 830009550 644906257 302485001 781331806 524296225 626759294 591929981 668361924 778838502 724992875 744092508 607779860 584858471 432583614 602970104 222452577 889341386 732401345 12446671 987649638 307326442 644494791 939958825 430389602 306423676 464852983 138575040 168321488 737218357 640817074 272361386 569249238 303245838 809103994 186960733 153761465 121479160 42442819 318824600 58070770 265013534 37332176 410631749 662501067 469163262 783723248 952031105 522280978 325502946 606420107 409131733 294438346 856229606 48897994 869116086 499473860 938946505 832301597 664408159 918864000 743175919 438766599 99275936 473662095 994190317 800291885 574423689 611986630 12487033 150842498 749831729 140404189 439593848 129001886 331930152 339808119 978790243 737334096 453173365 900442920 743325357 809829715 706073178 919494232 789038203 515937120 1670741 370009821 447609840 629949235 25297770 987266807 883836910 857980139 772419692 422484567 979630352 417325857 633749484 475256837 71307185 25593611 740208953 475854954 247083639 326637204 120854202 323248475 80065504 804031795 865839775 824792222 494736619 790712995 191408850 316752180 376113099 432159036 99801145 3981938 852964402 833190938 710252618 481659661 144648454 545664178 225968484 608906300 561882247 391139572 143022921 138417917 790742394 465077524 812020497 765852028 429356415 884295435 139278503 91944 17664091 136169819 398143271 348731916 159508832 613257149 974415196 436872940 596179745 373682998 674550462 22584078 605115981 766010139 324612603 340612735 224607798 750542076 993337878 382105193 395942383 360798632 590678470 903358618 492633326 498067504 604235196 608663927 924007824 682840688 538034070 266860132 551829976 573545939 130655659 593501107 80676348 598701570 744189917 555501990 870750646 47805645 222881375 548597422 61538287 154205513 373188966 390542550 207980069 124072448 536643828 884483304 230384286 708202905 585418890 787367050 310480850 584025815 119993981 631641334 147003886 98801093 876624506 957500096 430328171 61760554 8085499 561382858 453100204 854698352 134618964 755353961 174035691 273558248 920921505 237082180 841512377 299258109 72294765 759123606 224018442 840486451 934779717 912584824 14734088 972885132 291872557 268838073 139358031 175849423 519405898 835494541 449193480 136740456 607973100 729194693 186380667 530944458 205379148 617118971 815408391 347875682 906641876 317145997 996313479 190214453 796010056 332070256 739127129 726041592 291987273 387398646 446751627 923560340 736706027 535102013 994786282 882050239 733920780 797479493 465810611 253963624 828866629 129524810 164306147 199921273 880568930 823357773 805665011 36514910 264829035 290240157 504589363 560628225 300735114 378743028 220824299 773513405 826060250 444305906 73064447 751797249 511108616 395255769 642847600 870585990 241016227 891104519 908199596 851264598 447234739 7456518 942069011 313892834 489856441 71755505 741277317 502813814 78602341 150469477 875942643 418542206 893524716 321568823 578012019 719732234 891499163 84685632 189405559 86064207 616166041 906151342 519778167 784635765 241871054 656688712 25092967 513430167 399172523 970796052 54501202 957375399 788962318 66650278 154968479 74542180 746134926 733657225 883188160 413222048 801159195 33023368 737188828 938689637 176929987 683279725 114155412 295865197 323889183 670937668 377002282 857854683 526210619 68509895 112120962 483529878 481271434 883160942 753776438 317465994 356388424 938944311 242276679 936708460 311421818 487422731 625863250 850026853 891622289 741214955 577603112 654529582 950181472 921996842 736041639 600444328 111906835 470692949 944675489 284409617 885501375 693514725 379088000 694813970 734995128 369172383 837414272 853232 388680696 56010328 69389540 41845490 193106685 447445091 225106931 608214179 628764747 277862993 276380690 756155776 586201067 733868790 563356875 727929872 199770974 297236921 617410606 678826834 268984547 366430248 984896454 540768019 69870072 525322126 223908967 661615454 774805194 662377020 643800518 365243955 861489567 278749078 990660045 995918889 942496147 538523039 738653154 121002096 635478091 683969880 431865791 944443127 450755936 635024464 390170031 928974283 611663427 948048465 328793147 148115836 17423701 614923055 140229321 442885910 869057799 489212323 66133066 614601485 988917018 907440109 472799489 443625422 507791495 841904621 365255414 644044418 543223128 113422124 514910711 950784615 203639924 529117654 928298385 197343686 131709896 216068382 557405622 509537016 974273600 420437719 718124427 38095189 485577423 889056852 467700897 313040841 193173163 786574423 546517817 104859438 24911295 813021998 548656478 981265514 377479797 69694419 30547195 333701075 664899385 139899879 541450702 293102327 899554210 609289472 815510937 794632671 985297505 841872699 84650266 468520453 13953425 427898746 813323727 43028459 18446232 562629700 111545482 748501752 733062937 931688613 185414530 243716494 108443551 765482166 391717300 297840321 968070963 862235439 663767468 508072630 343507557 113923591 780079836 736080049 194231041 318146129 264299283 840556566 478319412 589716793 101279950 368847245 342077761 831489878 910034891 700441827 714340274 491158074 399361492 121599349 875349933 4279822 747781881 711172506 850246359 11307461 954223296 926126963 197778179 527592573 706635947 36733398 528576221 123997137 547149495 323593079 837165954 947665702 98737829 742582852 307520114 406335191 803248719 362796964
Output: 4866627

Example 2:

Input: 1199 700479905 527886305 311638678 303556371 349163541 623651322 499328183 851123368 962319563 951599069 505124878 679988630 688778769 38446384 5487821 979911612 209253678 864948668 964589132 111064038 322848292 729765225 389678240 362004300 92439524 779907112 609746262 576327477 83967181 52300783 258408488 438263499 662185868 206444317 994885479 245545434 897266283 226909997 51839754 133594130 457117026 717743092 51581319 22274640 624446217 898417302 932399158 235292586 902232160 517774551 421530525 786977397 788877944 363004344 832328184 398528345 924813995 844604383 266197083 66079933 784989720 575646598 597486383 242958463 871638340 750708931 115122417 959471880 102409033 389581990 172210740 604689913 119340354 541148578 500633842 37035360 221685990 196586834 550192457 203403617 689348869 488984572 237525513 382553608 824414223 652040842 776687315 563302271 347102051 329192154 252578543 345161064 907102528 771396517 890882892 406869765 59206930 810839102 306974446 858861106 758542416 111282543 27170044 65629309 961864855 396115005 571914343 748679044 798403869 850632953 461206412 461652119 760084893 155796087 303506662 534903419 1069695 221893007 913895725 37394007 779163821 631124605 973105353 639599798 266400807 748361759 486532285 530895915 413272785 606649331 285802876 161421016 345266448 302486579 147189423 953310026 432678667 586642901 324072732 110247095 722029002 676104967 555271513 802120891 627488687 35852329 276372556 360609148 639316671 275510663 273038313 235505828 963900936 985859781 410200462 954297241 349316054 799163809 17252810 695570730 723398478 445319146 710756839 881714607 426960519 926416777 988417103 884934222 411448523 419709857 817002828 435139738 658637580 629654244 394598407 136045687 300907747 944197400 534325173 554853366 716826104 93007164 793409102 802697794 614690004 786613957 983452232 613468795 969111431 179089248 276060205 597376321 931743303 763194021 768380953 758614853 54058099 674179807 343829719 828813096 81280934 84879493 417164342 496163001 813612140 201914165 372944142 281680053 327453526 404466008 671210372 401931170 557892875 838611202 32700131 572105634 739490122 87948754 512829814 127564328 672089241 579437404 425110189 4059484 920017848 386333963 414733946 456092533 631598736 384469270 402374063 459353472 574204669 559339890 141053456 496693908 430161772 741841995 147290640 685374891 578498070 80604029 606738461 519284362 54849546 475113471 193545924 617057577 343073445 853077178 255481459 700848798 436973838 289468797 684637848 93506411 830466413 469044222 491156153 591179042 620239918 396764983 190480535 393035873 321166277 760517722 956738388 692698992 395751186 9729014 877950533 387517902 629155545 547299257 457024026 856156027 785352440 856878144 978962358 294013646 592272674 157129125 848116387 465173282 528121129 446795237 291001657 289046775 288334530 19708665 88889664 270203906 317294776 438989448 564451520 747261469 10393392 66555713 649941330 687131981 324585704 702164691 188155859 744852158 422769107 796896317 253624879 44558243 283584911 500066387 51698421 682227169 190131576 261007414 692916649 990519432 254744652 861364565 191935380 420287671 816272404 382594368 46239278 534088063 771466150 120050157 279783655 341333829 783895552 696997629 710353274 994052686 689832008 307234035 46065649 403556131 132944464 671336193 525417186 444094872 183508029 11619585 919873912 500877822 764365803 362410729 83950933 364882197 159311548 227730129 941771437 716704102 518271522 605027153 465818846 394672991 725736447 771436337 622119052 951012775 442513221 223024750 710789345 236479319 299934764 553018797 381521486 166951256 16782199 884527497 664015768 454700450 971705527 767618346 516783310 412367945 891954108 282788740 970577406 105453934 662845842 908304614 214219433 869358488 605021540 949044962 857766817 389451506 857490426 754102145 691743758 594962519 448684857 734105228 222817848 908035407 694508362 501545386 413454988 487864186 606059175 695332269 782566269 872130597 156091102 616085697 378885935 880684137 770027883 507382807 663562515 997821722 174215908 520400199 853598871 597927828 621882251 391781335 819285683 791372507 913058955 353128848 360226354 329784524 267652966 455261519 412930846 450985999 672245971 877418772 117266385 264275256 375811870 799839787 588589968 561791116 191944794 540472296 475248699 332929065 23530275 505633385 172127883 51093968 802564973 719825512 464057825 809993924 659599470 427277910 949981699 979679880 159744797 697767897 804459856 900671067 652260768 938642743 217646498 697845218 345775824 981074734 521744667 979059741 674386130 351148437 860461153 482914827 125485082 524291783 151535845 840001979 69448117 829700568 15372777 475525784 361759705 817727508 11169123 517940313 840522796 799104641 640864444 823202281 719854874 524972090 994385505 220036032 381806816 413786351 671290737 200203523 315582157 883597997 150853632 410041046 85128794 295998981 263313180 874021751 725520518 511621293 416645142 749794176 216231413 171236899 278688433 960715496 102018474 170563611 508827432 821919806 509815776 640413654 978261675 210776606 775248547 292517621 613711719 485761772 823731136 442214289 705521743 268222295 684530827 455844553 723001270 112523109 900981895 644447567 804843545 70938910 257463865 356452367 717124170 945288529 55847156 628004992 40945157 184479270 930165658 115428459 116367590 122391218 659313575 320667753 358117336 47285713 534138716 359276246 770347294 329347822 155986724 947385207 667292950 476006695 208522406 38427177 460827616 820683127 394985561 684432134 784933146 850110864 498495817 132581367 114340714 405252367 82524893 198489389 705761160 2996571 954373779 991705825 177719365 177102165 309574757 818492856 691972594 563034968 598230470 293067853 759424474 956930938 52841773 183512860 751851426 380344274 364420264 126184681 94480083 113908105 279214994 792195448 640810386 678136647 233033404 636076518 751981049 78769531 471816720 346773502 113881073 281069445 395404649 864297146 642649700 660022321 879220130 242140362 221277946 240967869 349934717 9942208 305433714 803666998 824064489 503197148 998763742 867683143 636491198 776520854 533349259 85367083 441354277 495480726 93672630 563096398 526830244 133479021 742043029 143269445 897966613 677401363 722025908 891163415 672136658 29707245 901567281 517364022 167250076 554936208 996521471 738273861 308812406 15446428 864921413 42504307 206128719 449786997 756977633 770939571 795511656 375846748 256772907 822023964 114253950 35414346 870839747 159253129 833546342 333341003 122446867 485575953 241037541 683057702 270599972 939717362 498716564 487608819 79894844 307213692 152059286 181214332 145814324 313459514 638940198 606905116 796678620 293000903 560223459 121573008 522617202 481673822 238521545 406763659 993067140 62047146 358152647 276096547 790139551 18721756 575342235 219765060 892328374 352661340 559210723 946831736 134281025 258072363 358301391 907258354 207069135 784644355 815409168 470269748 670494951 643327748 39653389 694881318 681967499 795650979 408381961 615119480 774513154 734331735 887152195 278354730 59291314 788968468 25928023 945340059 793572275 528864090 967914523 29184408 988369211 885977519 798147681 394545056 633844653 321029806 136590893 781085799 742054825 907719061 981299713 765367322 759733483 819268504 446851078 669678204 691009135 182330573 421657184 457233337 837588581 51423291 253523120 546055660 587550497 852571182 648085695 844761105 37109603 363943223 98709867 18333437 547879424 335642657 434842927 529866305 196677398 178652203 247073767 177247880 578654946 8629578 485512217 65079023 531097056 -757460 669786917 778541123 961950798 945323526 521560791 1746528 886556073 228660894 889544741 969413613 98733722 811674911 922960113 674493699 231153396 19567551 445526185 450264930 436204933 358715082 461731891 11511930 53355234 250700246 261123266 992475475 85330232 246902397 878838587 182745921 611097971 506780910 674438944 458971751 372253305 107224355 24018300 160366896 742203689 439859285 31757376 638675420 37898746 377438464 659745135 279387760 121052200 273166769 736836848 377696934 514313912 860482796 775357496 297296534 311844798 703188148 396809932 988732842 953661165 916164516 800319371 856708775 661540927 995494107 800433573 594601972 15906027 197333435 8480360 307418026 744666354 804235535 682810805 625660437 660860090 952258328 681977272 551861732 783077898 757234305 360483198 791448587 644513662 837513267 453620185 131234844 529797373 231683043 285766181 666757892 372111035 173375211 145308439 196505065 622795922 614769730 101013886 415638677 159953543 204574088 824108353 185029938 19550767 969737758 843268259 517862489 685876238 833908343 530516973 268085873 985896367 441686840 135652135 652470949 976852033 -269763 833654296 710728457 884356224 776043262 739843920 418412888 734906237 541174498 792976199 640832712 398148087 514962223 890580232 598813940 504771568 677013745 798619371 824484249 491257741 588478188 724593062 816019979 443479310 156690509 189400587 539567316 233613895 707145794 377718371 506742095 254209768 259002117 392461677 911374631 820557330 714011793 125243565 87364429 310843095 366999180 71167781 736198343 482924692 326363964 416990688 888647964 821308066 734791856 727498277 193925448 417949482 293692119 440522997 273989225 116038153 131355175 379348605 991381753 249799425 248245081 962517244 917753415 324617118 649438239 40389463 159675535 352331429 529931458 128188417 857323785 634940447 10493731 697231738 894238254 389552752 612147877 149553189 761014776 463870548 98745691 828053487 593544710 479451272 199724941 714076791 206906227 342936509 724683376 192672097 502545221 120765678 317018670 156552365 452799260 397171953 315848517 216870601 264671153 834294153 265785855 984482276 297764340 59897825 791783984 661247566 735698639 614510470 872778716 381036433 526969226 599089564 969393626 239300601 487335973 564683059 821159742 392698369 449155921 400875657 636603462 227037354 201072235 692274465 757810758 411427131 339093941 746602153 862333137 619036933 308655249 997197773 505434646 751575712 789543783 82962297 387276917 727081698 310433779 79762031 81875649 132671271 944520471 122197282 117523865 81560876 799622445 328775316 760167032 951489604 195892327 685962985 340043573 617568758 593042542 609182081 681011776 707089055 896276543 507919602 675681802 707415323 182789000 501727379 924117116 564988211 541484309 853861170 742942709 699721435 344769392 885544897 949618451 409929440 419255948 577917991 250662212 762049521 894883562 470961696 916586470 196795589 370266199 106077030 552033844 468030454 357947272 356428645 798888773 113411851 451369433 878582380 180141794 987410321 931161215 928427041 556029448 699823186 796395014 392903911 910218616 700221080 262564918 846794833 890244591 406598287 331784973 267708366 163872387 915690724 552403037 710719002 328671981 255540104 217761249 397803060 826530664 119417435 839598623 633935293 822563148 654358968 641003664 699180897 76283365 797709240 214820005 186438722 740933017 877498792 456996162 366874204 323541810 250228805 889600045 472412663 760369760 904631027 156028951 641949182 480197268 809084113 371861601 912664558 540606874 157467518 954247279 812343682 164972457 414351763 135312279 229714182 444264568 673894785 268942826 966055067 732105745 334695427 592889002 398592834 510647266 150737820 743094945 90740601 76686285 609358249 653663367 428529285 335344225 857962324 399228521 674514250 562442213 824400094 470558477 380056834 633633843 696228647 637466281 356214135 580692037 706169843 572395175 746830500 80709859 470752923 186022378 446706614 863118963 398050565 59618720 22147507 470072044 589263676 969018457 27767701 52723580 428881992 398717307 587129307 365428134 520428566 567911705 608696320 939678996 947002661 446732928 945141687 442684470 600829250 699010935 116854407 649098336
Output: 164670

Example 3:

Input: 1458 622164396 297304948 246103775 759749373 596758542 515341109 24000425 293251450 189275724 408689652 458064955 125350458 92520556 753902522 145206879 733706108 191869575 178374475 315929362 258681915 87737769 348432008 680165881 673654731 738089406 513754950 243329191 650784133 833305454 49586322 416612044 839181889 285137790 103849823 311383314 285360406 452392823 74992146 359253813 838523776 661669328 65014684 925933789 878829025 917264186 905196663 12129995 754388635 814910017 719443546 952887154 167561217 674831190 244930321 624228656 62362551 810412038 740797002 903613152 491361292 994836714 801709346 64605772 247764830 201075872 965709365 285081871 300265914 596273015 116334931 351532815 831379935 268464124 119522298 553098777 240294637 335402828 260189033 944474933 648417069 956913150 56238126 774647915 401030761 21313652 477215024 840391667 530304605 341338398 968753362 483388265 750953196 934997781 248611462 775154133 325689186 689115886 663322628 286354076 490101457 692598430 862096013 187480651 375375555 310125679 702123109 979567367 199461460 325204462 377239612 964902769 174434917 782866493 979983302 345157907 924227364 558429 874138446 788698701 432825960 222949788 14519608 385157220 912086819 2239041 973284963 940172348 800018439 582975282 244697367 209345713 658570980 635945220 714204859 703683835 897874849 713140846 190691934 225475178 833211972 215611129 133607514 958231322 499342980 197688368 983634511 628126149 683702021 400167361 764034664 941619112 768815848 511301028 508545845 486016229 293851375 530208252 357962106 299502869 129607782 966096773 226323567 776170981 334431209 452515933 763005115 637614464 887198109 703658824 398148628 86884240 322040872 832703794 991284791 635311245 232241707 728454250 462375311 740959842 137475442 726421412 485946021 591767467 102870936 245899763 460838183 136263683 305788393 105687443 209814601 144840101 381272579 722066967 379765110 409066264 841434797 730334254 697008476 252303664 87195350 432347573 657475830 244450098 973291305 763926470 162258238 396664855 794808669 579538523 187403103 666635770 390110223 923673657 638931064 451256158 488830979 85358188 137257949 352939489 154956753 758535862 217863234 123446012 259527087 431831790 27593290 308578400 553640280 89694723 818251736 445910191 264893608 541557250 851539508 434207779 62321182 314241353 213481361 658426683 933879747 504498879 165595527 702857175 87852280 191915937 653970904 707510478 487219782 129098520 312972770 348337659 916222063 124854523 661899410 326130106 758160031 810404523 983535871 639408110 49894227 501132332 372156616 986574456 562706248 39697494 314228154 676645578 832667547 54588963 43717350 918016482 761573168 740380176 885151849 929492956 16531647 627097809 345869042 223891529 373931023 838427213 79414953 206798536 245670006 452209232 868665903 454986787 161244242 417674409 781181702 285780626 448193094 336235624 688718041 618196610 450072639 192862721 834228227 63486085 787584861 550170769 36782621 599960655 500451721 542156562 823424454 95554827 885918284 862225826 114389018 751340571 339063377 777863346 476871728 428617817 336729675 80764361 830917846 697963867 612188802 712712671 249619289 725593331 29207791 814714394 682865220 463896732 93569612 477384287 498184697 680517811 832520576 419528170 639512694 67641031 737759550 72874281 318377165 815304355 735580582 394165275 383648004 18826147 399223097 126883352 274805595 811544559 440754880 929738822 783762115 386431331 662866923 967180277 732478259 684137460 398984779 900995350 537076295 533303897 866841015 147142673 448829505 873509622 941330889 596108941 862556692 844059571 763135705 120372441 720283005 942457731 617899859 400894069 389993730 387233027 245661510 625179960 649035959 164279032 998965355 217220200 237098120 788743510 521417509 419358652 650990462 131000464 218355272 436155735 146023287 255811478 405134149 982742143 264102359 661483867 680379680 18799793 349030481 965344498 439667876 289403152 726525593 579305064 476445111 273674064 804878723 55001695 309292920 177268539 861812693 203886026 275376303 753277749 385195315 247021696 254230201 361521047 565450665 673279391 67747526 602910454 459126800 521776315 658818306 755803951 198658912 10212493 950342159 225246029 229482791 567252139 549491001 606293462 44330541 845712361 874706558 742625499 746386842 231465307 1857038 699856824 687429730 853811145 804219154 664304962 901414779 32751877 901683427 818299041 469530197 319608778 891376596 941232980 803398659 908214072 546802133 86332355 938353958 923225940 735248340 871897261 102212059 475458036 337649095 693250369 938653285 693997966 433987227 987579132 112227494 810837776 521466463 274569078 555365079 464539710 965088581 557377152 244259254 770527884 983470216 169697800 889888953 621544727 57909926 557338742 225404057 473105872 967185854 288379198 912535580 203320470 175423109 585085167 113212644 92010670 59438314 260344124 657968254 773019555 992288383 660350600 21579534 800718076 935181159 996507183 992208032 532387678 736124464 554988477 64735478 683298994 682193432 618007199 498248764 407297991 355955803 801389108 488488220 611697080 410106706 913544895 370565131 547095030 274773300 789177661 570378446 993427523 933266006 833880112 884135034 773585864 922938420 186046141 649155178 167983007 472896364 305696023 770395412 403264699 749286436 205323585 898992906 257265994 490569330 918476407 376357508 126734925 345314852 541021136 550822682 374883090 94977120 925660142 460261986 650921224 471965219 674917156 3591322 203490042 640776940 742413538 629293808 822799870 644369132 454997505 328911321 462347571 489693480 600001732 871048086 132897650 697018842 431847372 224657693 357011239 596708733 84575729 47690687 434600363 335683451 448607732 232517141 213176575 739597716 966858845 448683483 663424158 362536465 849367589 779949825 296431577 733283554 826711848 274488430 973950240 886660988 715967953 197357865 86163350 715761399 975147799 518953427 921044275 892161838 445995398 270317259 908368652 838626919 398173987 231384710 614297301 775154079 480342070 786361269 492373244 740960065 206568089 211361097 564604919 228855039 130021483 762640534 879680867 320834637 229694781 239507277 908415437 460084016 195732964 524578146 820036316 491068344 936254097 110821406 84691126 51325431 519383502 429719510 900065616 396553221 101274798 591994199 729272802 825859928 409581532 601961910 715488319 284322365 743103813 187031748 284044210 557228542 96114461 5779662 761570368 370091519 711882327 358191345 9628797 650742327 326862558 618056670 403630725 436562248 595505383 580823073 851726275 816495082 322223998 811192824 832165285 117800975 943055305 676340369 14193765 65725607 85594862 301515021 803425741 284957186 778209577 940174569 240572079 833398482 544090445 843663143 835115768 983670643 182953135 861886205 417654598 318221879 861085579 95860269 973898216 946700745 2160624 530382865 659670292 601357752 689662580 418602576 908507527 457018728 287120979 32554543 759725762 428382335 561271374 347171176 128695242 376074050 234583786 403393482 522632355 578993029 5606398 379901209 696772994 513106803 570655349 108970251 559978780 371268462 357314135 931858668 43020413 494491976 329387207 229995554 791816737 480001267 850054801 220942237 76929033 817959680 49857350 501854109 874965411 42239690 721389786 713708963 654273217 802531459 350297666 741014706 321174887 194382629 908883071 172307485 833030796 511868346 257962373 968787045 256531775 536691656 409796081 258600901 143767903 711866528 129697115 318122345 718852015 614645117 68994372 408795453 766169746 830729839 204604495 572026920 218021894 415005680 546384934 983064577 711118383 639549853 772104641 461070552 945417145 150883247 640621061 280611716 871019753 236413176 561247764 338757136 113121807 959325641 707385107 632280499 266081656 615503545 695846285 964105349 546336045 447659055 927322730 279069878 38316768 948525683 940922804 979309621 658794742 963921397 94372951 28953651 850137075 241857046 90478523 758209586 3910698 286464006 934942501 479971541 951551357 753412210 973138266 347522056 625539719 554342535 609632843 652510313 200960449 975018607 599305141 450992647 350493814 238954458 619754985 223622837 788896329 31933410 71926755 480566965 63254153 166077362 943188586 394244343 221201549 692076270 575832489 228764344 218002199 399253591 921385185 864018912 709539129 306055861 78591396 920978288 724086304 481268354 947199793 560500784 732834508 335314285 997064294 164425130 839032043 752098316 246400443 664051514 755193534 800594838 521994285 887987767 191796989 967795010 220659846 633949526 712867687 791644969 537823742 664201154 645288385 806585327 66581986 976903586 640335891 122241876 758564586 697360965 165783288 678201382 3018222 780530561 906954720 491905034 837909946 311499042 489482776 773688665 7457743 692276320 413321646 537823133 172829661 492759730 801064732 663330854 148702077 617653897 672994087 640142076 533046074 54722489 998514662 207549239 48497143 651889351 681889772 159655001 35710159 559926893 856389672 422200336 928598109 921711081 467104236 393681116 184972627 492858222 815770192 908262733 920108889 950896136 868276650 844197675 429690616 411109680 774834767 324976174 48236136 307053436 471490131 684530266 753477055 375211896 15490247 820874962 729279383 355661799 817852146 47288400 452769044 477261444 136987040 986885110 68127587 207993136 646412398 3830442 550958788 348309923 215137155 793256827 344163227 185192615 863023520 708464541 628559764 557776625 732597086 406447102 256065292 705306463 139460094 477569374 257388831 294172913 760986751 145860145 889137212 429355375 467131597 224564647 422919458 604996328 324207849 822923149 825955778 650220356 369933106 925791773 676769491 265230941 285214642 309135493 582976527 688751705 58714969 819311751 883131229 407931624 119364595 159431185 651615783 551794801 190486397 604655442 919480031 548472638 889869351 40259726 310703627 499479686 240556526 670439730 260704202 58034932 204573111 354651513 914500022 447047734 863399995 582095909 419951060 855354510 706694320 920829707 437591160 159037761 293631311 67180803 900152117 137279132 362629222 88003416 637227065 762267374 727748335 941581152 134796718 460551866 482234270 588204278 906931025 46500347 471980421 880010555 704533836 863748876 586943593 548234362 997090022 915643377 588015334 21332569 728372100 353078422 651243542 240962384 804618815 783944082 651138156 728997244 399626106 510478221 948854490 779510078 362626794 129246173 97073173 460549661 858532806 670661910 272713251 209448747 107222715 678707176 490548151 906771168 482190510 428113694 865889444 107600131 338723104 479205962 715339410 809737282 814154111 402915030 974171215 525331751 445554403 677822959 625975098 374248534 212597871 509664838 767760273 527272000 595789391 152331277 96705568 862446836 730218252 243977643 524540199 773334801 319886286 949121017 895539295 435379257 365603860 573848040 619292713 111535540 286568319 135764904 623277260 705086960 9265386 98200273 234711356 79338927 528905187 216183885 820531847 963393173 850712700 612715109 362002469 165063256 232322874 859309125 722227284 179276754 285546740 661385978 635412616 330290610 793905824 968542058 100007869 743716162 853794443 821468625 758436974 540304904 371216773 359890174 271743506 964902212 692366572 510870833 209805420 727994823 857088688 965432480 232656459 433725876 872556343 327794244 459924201 27614272 124675593 214936493 727573420 784772882 67426100 363737220 500548987 374308075 324131294 221831343 665507552 507587591 947294715 631346034 330885158 924593442 628388003 769059534 290980639 691130897 198774149 563707994 192826342 339681142 806280840 681580179 964284243 765688523 122831201 937406347 81622959 782708281 420469622 657480847 733492365 640863420 240473060 477584624 177000765 991370108 995932329 486858612 406648495 413715659 878839126 571700684 381310085 188775105 512650914 48832098 951853122 633601178 322189732 767105066 233989569 65712156 547549270 951276175 639602359 283538799 521686269 1680631 22316969 346869991 755522512 101704624 488159753 869767762 315883486 822624805 207389204 607935533 335916359 280400487 956213645 288537205 69978740 192781437 695931504 854498007 38784586 93730011 561039075 925469251 754920587 713318385 443999898 333950088 605190824 970657455 58356831 147147821 415362550 145230110 341385349 702203577 690275165 306623631 807914910 509316584 112589051 476148251 65371834 452846851 122798003 825243693 828963823 954347333 274637635 937420595 929253073 74605833 988423020 423288186 392279595 206314414 395658980 576989903 233125574 761851889 228089780 743105506 644714825 477315949 672647523 559781706 335903778 378339239 436920835 142262070 831346744 467183028 437611713 835348105 173812133 677533209 50440228 264361660 125976789 942288304 159761293 350378930 849068622 201762744 47728793 856847901 117447376 579059702 272016461 506841267 370085395 358892296 103152105 68770150 100132359 628384234 333664328 764844341 849938611 246969871 544841328 210025302 844661925 244902373 25462429 365524098 439293641 380768710 77722357 537100153 26726625 789418869 600298613 663518142 78504921 134351114 676615641 767730820 313783874 146674109 413174528 488829486 690609417 101460700 472079520 583977912 531744988 494902725 891023747 693640889 422509663 186004864 990960529 531831755 425936239 953594889 736324948 298059606 765971283 312696004 985201580 595128187 417304959 813912682 331808999 957922347 390821008 23898081 427419709 143299969 400984520 243625849 279474187 946736291 181262528 180386456 978421576 447147336 791658755 301971228 455100822 20019675 98079184 254703580 69294163 863433231 687520128 90388069 942991393 329950276 306080942 782756229 246105809 581059958 182601421 752637765 824142214 697211568 399931962 402497085 962895547 801512549 658033545 999367533 130966098 151917432 389721845 678749502 885359169 926858807 930165993 478665654 977928887 479430497 611879513 680876405 301133019 391020405 614634882 949072495 972341284 721310562 747065716 989463147 196116700 572861237 949012821 992354475 752011842 168960590 679437692 187687181 314613246 777794713 437494764 228064563 836733843 137942720 763410801 8457369 983231676 483362821 802824334 527028913 272938452 439064084 634182397 937869857 483506509 180558796 650118817 148535958 115251620 947015286 285442924 504928490 47815946 58577538 441442775 919524254 315300535 938177042 148961577
Output: 190801

Constraints:

2 <= n <= 3490; -1000000 <= a[i],k <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
The Frugal Pairs at Tidewater - MEDIUM Coding Problem | CodeTikki