CT29116

Hema's segments Reckoning

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

The harbor bell rings at the port of Emberfall; Hema weighs the day's segments manifests and starts the calculations. Task: Print the maximum sum of any contiguous subarray of length exactly k. Input format: First line: n and k. Second line: n integers. Output format: Print the maximum window sum. Constraints: 1 <= k <= n <= 3208; 0 <= a[i] <= 1000000.

Example 1:

Input: 2727 2669 892837 165259 97706 833769 760437 576347 700055 693449 543358 641012 259090 243610 367067 933907 38539 38892 366306 374573 834431 845328 652119 312396 982242 96845 337212 386989 296128 498350 486991 180781 26357 542828 875924 663142 780673 847016 631290 213295 623621 542115 109306 16278 667584 445683 465908 965512 757480 969857 827385 837709 381519 652423 440124 765113 679839 495388 862591 911938 394637 165588 847993 555502 731644 453438 700692 110771 175826 316456 502767 614718 609387 289922 112338 738613 567073 432256 529549 940469 942338 314833 130923 211652 945541 545727 131022 78170 758290 260667 856344 901732 875959 325490 299936 309761 357855 64861 236119 709129 252245 729460 659712 90941 186661 813738 34502 853755 62307 586478 620872 101379 972985 488835 93392 32291 58063 980307 281181 434035 876533 908111 744435 182844 835425 265962 791809 661995 740538 29108 101777 672417 870209 345918 157167 201613 789251 592339 450641 874648 498625 30411 112987 651499 391295 363580 366618 611978 505046 230131 946755 750029 731223 521077 210046 334167 765744 483021 566669 871488 20673 388562 536258 773398 813468 277283 741566 316138 536725 414584 877018 365306 934975 493881 930017 966312 743476 868516 679162 787645 124694 752775 992693 848332 570639 396012 979427 122120 18885 164641 522372 625888 713422 117939 6691 659177 779851 310372 528463 722948 358029 993168 589125 613995 220774 717142 493429 795111 179694 70319 692647 275272 11023 583357 628592 60659 6537 36223 495621 302424 331014 227388 851301 903045 96973 193172 104044 522416 444894 396631 333999 647399 458555 843360 844474 796570 340671 585334 743873 824955 257341 461690 73971 912578 462115 97954 163930 280454 651029 305123 943307 718229 117201 935885 854236 142134 636440 198399 695775 724066 275990 176495 898284 548660 864411 31054 892418 451843 559336 106955 815158 630273 963157 793146 642073 205749 702704 283541 773848 210812 383339 1326 168373 117607 772875 275765 900188 595733 535923 754144 541822 993896 510138 74302 859665 246132 406462 188284 54884 498637 188577 900320 764718 220011 568564 98225 114018 40386 239259 419622 56733 810334 96841 50360 309452 674909 935109 568778 671076 370264 446237 270968 571406 369852 37889 118633 60889 831643 551528 254871 202195 464305 340828 524999 839310 909298 560985 133751 561812 340843 821770 659788 118073 770044 800544 219749 19390 665678 474005 517267 787318 331125 973476 351960 489894 926801 863036 250544 720723 967109 211411 300294 396059 73182 351378 539527 13555 23860 732628 965698 454797 609046 229350 140675 887848 854703 745347 894006 343418 194914 844213 442351 876951 132222 272876 342016 30500 255092 9230 532188 766953 700287 260955 924973 100433 955859 383122 189035 731186 905940 387268 21889 405407 592175 556229 825501 445279 7518 428940 149918 153026 64788 87557 924264 745851 364022 147686 130783 105514 994923 259230 255822 592944 565895 746375 41646 163246 770011 839299 210262 228431 644129 468821 906058 122656 923565 791299 546344 369743 657017 947277 315279 168344 592368 629428 704777 738624 660437 527522 900096 160447 986833 160930 935253 218501 509673 700597 344083 187795 530563 63743 643511 920340 178479 609577 984683 332263 67442 902522 73477 269473 24069 473041 978729 22527 35631 556931 744506 535747 721886 716198 42005 514335 832310 266229 299637 53236 868737 776612 125351 32735 950736 205819 794188 714323 1469 696087 242103 897064 158564 396240 3719 620195 366389 223242 989740 690960 63609 73933 387731 476584 312336 924756 895952 399014 890667 121383 436509 156386 232776 482219 851153 476602 324446 497489 730841 332315 768625 360105 612706 174373 6432 49936 216967 968566 147688 154112 849217 714193 665900 188872 15170 295451 934319 523883 839344 327010 734311 248334 698748 300704 545207 651881 933903 113768 64554 35010 522418 834986 821589 881837 370168 562424 76751 503600 213571 962748 708907 994050 682813 514365 623006 944799 719215 248110 465887 445017 976369 346110 663853 28702 81825 553917 588380 577908 578326 618460 356457 184348 266321 722597 64646 156953 623169 996344 939037 925615 400294 122687 855035 289145 475863 828863 339096 393638 783296 914842 81052 562031 652801 800624 363035 727482 520642 666798 402863 563940 318245 943467 882407 228177 612731 299836 328389 532547 760330 300947 469018 856242 791729 767002 614671 746549 117989 119716 291968 865213 866563 151256 426339 74146 809825 647905 920383 792986 546904 161324 339634 42697 853246 406136 108568 247444 214431 175911 432171 931186 879877 269915 423352 314784 892950 872127 290949 556386 570684 148769 283500 799116 519718 702697 709944 163741 312038 867792 118915 5486 131387 72458 51950 261035 757562 218286 370606 704426 453769 761267 611197 591671 248332 600998 956861 314733 491102 216400 593474 496814 915997 399270 995690 702380 365374 631874 466600 809973 118376 173030 514367 140453 66254 397427 547387 357645 478968 982645 874082 628999 246620 348916 811580 274218 463825 276910 343943 857741 993523 30292 669418 374056 305029 946920 955066 711703 7130 552793 622232 74302 661539 841194 352081 353018 238632 388521 753433 32980 706195 246831 602507 166885 581978 367619 804435 27630 299186 85813 710418 959923 261237 566003 747372 994391 734517 830011 530921 700765 248974 207970 528145 745179 522221 574745 310156 424459 332453 425120 562251 412199 711029 581247 986445 407181 610253 932545 443524 733738 226960 424473 412854 760315 885972 235201 400541 586937 504498 290222 137508 83822 32534 296545 35674 731753 77217 750592 917971 644489 119519 171055 664630 965489 664502 40060 535912 892655 345127 533050 243975 871914 57648 841826 183600 113211 325312 830183 595422 280117 329417 607563 730752 574728 739752 236187 398756 525566 298259 493118 943131 88258 461400 387238 390765 198483 101608 998804 150467 204812 822748 889513 413844 235033 449403 898766 162458 881321 696478 492661 194609 187027 819636 254337 224544 926755 19198 795096 276800 964218 978886 442405 460472 237038 547627 507763 568693 663922 45967 876974 312785 162522 637781 867677 633270 805599 445165 303217 347276 411945 420910 784625 975802 905734 326600 850193 438822 201054 293628 900108 632884 573352 126714 72681 453485 796938 710808 640878 314181 357211 900310 322784 982562 228711 830237 196082 953301 642723 335449 9987 912660 777783 231821 836110 964771 383756 979167 641045 437822 344624 115750 525022 872851 4940 717168 709813 973468 517745 614543 999605 725572 684316 311946 926012 718031 992624 292504 187113 997627 147194 284695 978002 477580 492427 759103 252708 161214 579267 512103 834963 994030 81267 279855 944875 354813 844609 458300 176614 43781 823096 507575 868031 738795 734381 652092 798179 312138 256382 338389 412849 972922 335214 34229 706502 389113 613469 765574 717593 461876 963852 808126 22809 947833 860189 51279 576988 917509 29928 642919 427584 216797 704706 834336 841214 319031 882552 733695 173622 317497 711587 960669 910327 714894 300323 428622 262028 705999 130492 876893 458508 439577 642462 762558 508287 457343 162149 925628 448913 164345 294551 248987 156560 735062 735950 374440 264036 467255 546289 433175 222789 944829 214515 273208 625009 960889 688348 513804 883679 950601 916897 90673 290233 204269 546845 895054 870545 952694 629337 542026 976604 427880 551696 590743 641840 560230 333406 232502 388275 828335 215374 589351 45935 973769 213709 933427 24222 837588 924488 616528 547714 788817 97644 580407 991295 191624 561727 401928 375696 483534 321795 839217 131242 147643 627532 514523 84917 698713 59430 811928 532466 682057 775406 757280 261277 33494 319287 910891 242322 24993 372776 593647 199991 814371 754966 89693 163143 939972 122998 931688 906852 135850 21250 908128 519212 634557 17335 92485 900330 5615 570477 267921 11947 14031 204917 100774 54593 62971 408596 489305 326604 830469 270473 989855 962275 674122 872396 848689 994621 65840 659637 217081 388820 548715 231043 1164 328939 621288 905662 974256 683536 655546 355023 307916 199276 787528 929122 257961 108764 368246 374182 522531 875840 305956 392652 784804 305235 720097 23826 232855 307856 978339 907939 521770 105577 207243 184469 519237 38609 574152 440738 788138 976150 743748 131851 963009 640444 504647 96507 892487 106926 5258 450660 448712 90163 817820 823112 279659 523631 226033 874947 435624 269065 556619 822333 848612 432669 784741 951972 416253 722145 442926 850782 108407 988384 528174 208472 862554 251591 406971 429598 906253 615371 391252 638223 565544 633272 652822 996101 290408 820877 998529 905543 573771 966213 163740 878356 766070 851318 622286 474597 153259 95228 968426 258685 616568 87467 470518 44900 618042 59483 774198 600145 561494 975360 558442 830287 844576 133428 280721 261522 492121 270436 177108 228018 25500 160503 516764 622290 381818 582757 791074 259286 743938 800930 134113 101414 176819 32341 127726 216812 438170 620201 733570 560604 646998 864581 678509 856590 871074 278328 355870 21831 71442 490371 946936 681365 116235 993519 333496 446747 241548 20799 987343 93140 59748 144297 157974 692977 306086 432777 79623 20569 559930 633138 240092 702526 281580 112055 384120 53468 129378 178508 969847 706536 846277 32760 471330 524022 718215 15979 585441 875412 700899 286267 78047 233510 61551 78425 632250 425668 572158 825500 649897 628812 315963 480922 789081 988262 513536 550393 801036 457974 317468 871805 892312 32209 793925 64978 254475 587792 371250 163070 245058 289645 758686 51585 792915 938880 74520 837085 323586 230253 169884 889467 783123 645602 377250 963407 989932 129545 812783 893847 572131 70462 264920 235281 768584 155789 623882 256338 114245 965288 65106 278705 231700 375110 994313 475783 715229 921876 542198 207302 550497 440031 211467 218378 265085 65448 796274 145147 800721 360739 151035 571426 282461 778354 95464 837418 623491 558515 535233 491870 422508 386445 132335 496340 389444 850065 864111 130065 813412 760745 307306 521175 967459 363735 927378 993943 507859 940271 360730 201289 108052 96518 163481 931803 948332 262799 6511 220236 441957 815904 514907 952321 497368 806633 975525 993756 272543 955038 979646 275546 173122 391856 786704 346842 884159 912281 195635 59527 157286 991114 763208 53970 826474 421156 531265 112339 365641 778034 171816 129300 572278 729972 516416 691898 291101 130291 846128 870897 304675 630251 180315 883321 216217 807257 635379 823925 675099 284067 197993 971442 582876 44433 900045 190459 345777 773460 237987 623260 327724 846154 656940 437165 311061 113391 910838 931450 962517 123863 87193 344859 211482 700287 679886 39772 526903 555744 978889 12884 89925 947527 820372 218637 138125 603489 818080 720933 999841 518259 208896 163000 400839 518449 104200 99941 279384 739241 493520 624364 94324 966218 918166 932291 952112 160611 115908 117368 647758 634360 964229 695265 518494 268376 198937 740096 190969 165017 61440 179969 35505 267148 22422 979492 873403 516515 259612 822214 626240 309681 170132 736149 734987 627999 221209 455474 434976 176714 786969 552745 582296 246185 673104 679297 711374 797044 498870 891744 776110 57714 52929 712625 96639 29892 347893 635439 585631 129215 810376 851646 22629 361162 119368 470005 425500 438312 757514 550278 526179 612707 438946 43269 894171 578837 607490 667565 60482 782919 536810 586408 847659 218800 279099 783016 115374 242979 732372 338589 220850 577376 442981 483063 109525 686734 472978 900184 169035 497899 84695 116026 431318 576788 60858 192125 159302 72886 686784 845521 896661 359742 52646 147969 386425 216519 935498 307387 633536 959574 304658 179479 345526 622073 164998 259533 694432 480949 169221 848744 596232 603089 50418 839367 28808 554998 190625 558334 811766 516507 549002 897622 646619 669460 122727 344443 487984 282573 638988 479087 192358 959441 359902 76693 845618 352927 742559 108312 714171 349270 611462 169156 506498 342317 415867 514269 743733 362585 722417 936897 883733 415532 736193 643464 826705 969940 756202 168848 766063 324830 784981 253410 689947 778654 691160 825514 266951 665670 71089 667800 807122 919439 603380 915534 399706 676273 775184 419503 437966 624398 218543 447192 117503 397705 20551 267812 289640 831374 337557 804560 954641 141949 122937 91631 109953 681936 196261 931153 968310 662491 68174 976590 316970 335502 811072 308740 877375 55152 568308 721642 985556 577921 212032 200891 385491 255449 953884 791935 854166 849245 271358 531231 895494 612583 17211 309618 61860 276636 238882 169994 489707 94455 516626 335079 277065 916511 663682 698769 376172 853175 18816 146923 903275 609583 886452 23121 390163 486753 819564 122391 323579 819433 901218 3733 270531 989679 917878 873796 358732 746836 377923 178383 202468 261446 334098 19934 382247 153991 100567 927822 127942 442183 538102 422455 491297 170956 930309 383209 972862 322908 84071 990140 100815 292005 695432 870878 62051 309747 847180 407297 386217 242865 541305 604004 453213 95196 845394 401713 381991 821488 901576 608056 354594 94462 422784 610482 908174 181884 197758 538068 624834 359243 820390 407485 389353 467447 67884 608612 333320 141516 393247 729533 126224 458591 787921 982041 588324 286435 838094 167453 392858 629455 880158 601697 981529 269272 470415 543404 382879 379237 161268 820434 757377 133393 16161 93791 325096 999580 684759 676277 7194 646325 494618 287461 234228 793367 831526 370742 749122 374609 899322 795823 420739 217844 472537 76558 759637 764014 697759 687822 551884 319576 602545 467575 817803 255535 863207 133315 239614 930958 476709 27049 24712 366214 826531 3573 831115 894640 251014 341893 296145 231052 916608 617224 728626 569145 840509 389925 811590 535095 154916 40539 553254 634343 242937 60818 399206 688899 35110 822264 338252 595515 128414 43592 739720 291041 402196 476312 906503 8621 302279 478580 488866 37383 171632 787656 187202 152493 837252 775272 232864 123582 1413 139390 351575 386360 547082 867890 666796 434883 516610 835219 431283 693805 497550 560684 102831 790671 970585 642300 956317 706944 536857 768933 427901 492946 295018 814272 756619 273098 18844 69445 734844 125128 678103 593280 360931 555087 781978 945338 798587 259829 746843 578707 919480 279686 208596 992445 123943 224717 282109 189071 96587 151334 882477 290709 213677 847407 668671 569330 466915 416570 486661 834467 770236 486847 756753 190841 689825 881047 834926 997414 873598 283904 288257 628284 562604 753989 856233 8556 894922 562914 858798 35109 68147 666990 97498 582933 904695 463763 101083 589231 939652 724489 664381 54745 356436 426792 916369 321647 368865 492526 634929 974830 500722 118616 989640 223534 150739 433327 735445 250368 285602 510328 791233 478453 680342 412853 14785 364543 379127 21554 741849 391267 284910 263347 409419 897409 993048 123751 959002 157272 391899 1569 82472 389019 774644 460243 311878 961444 752838 138880 727541 635768 314693 26505 410436 888859 87505 381745 339537 741030 974494 484037 931189 671141 662799 48352 687535 785672 999802 970038 662885 564175 290558 553120 480481 154144 277627 920987 666321 762446 509474 675366 978793 385841 393336 420897 290614 643409 169191 335600 763041 454736 412059 674930 412381 359361 631906 454133 998615 940895 77240 793091 906776 637393 356610 913422 611206 687930 445713 14218 289331 851547 633441 844266 621621 525417 904608 201933 790342 426224 179853 49435 8603 692818 554801 529215 813439 942608 157596 12797 421177 560070 625117 240810 84136 495366 562488 717864 843828 643278 605665 232559 241114 772998 802309 937130 553945 114909 702850 80381 934615 849616 213202 382412 141105 976816 881081 111580 257339 869889 203614 749525 938073 615091 445068 175757 903815 593298 836204 829197 736092 832577 324476 488389 747577 822908 88828 661772 829540 257627 473880 503341 198225 452986 25761 314963 984641 651261 920358 865761 439195 911186 595117 268790 295385 415357 331952 820931 249518 880206 709865 208014 819437 775802 320744 372745 839432 180741 120218 561627 249553 73207 29652 899099 511242 524274 238824 745825 844329 379452 149184 222871 332541 263134 794654 880425 793432 946628 116158 797759 711527 824920 440358 45171 324648 712588 381210 202146 561620 364745 854565 237173 492376 46795 17056 15241 864128 281366 403189 915004 778343 800767 444718 794948 796941 570920 173068 681381 428856 201076 613905 9366 566465 825294 447934 615781 715309 664984 314359 567682 294119 458258 542848 151271 601579 772867 335351 567359 449177 873971 550828 298537 540672 497011 573866 49613 888584 905627 513149 642097 762157 911975 75833 889967 276394 364917 93953 726242 276586 244522 541655 165551 82925 786488 338663 305482 104378 938618 872617 923458 915157 900263 413256 150360 134271 491613 673588 486935 170676 608093 100137 534293 271156 767070 420382 242458 790452 201443 34730 415372 381450 624766 142776 110721 80455 106261 942050 711806 49635 455462 130918 542948 732478 335943 641918 304709 557324 845613 224775 522884 298238 6550 322265 757573 578781 473114 266058 822851 287615 337407 891392 186934 642697 274975 448327 477155 590898 321958 924050 910183 250324 905941 307130 206220 232551 331069 712378 971787 321135 762579 530533 868958 390242 705248 438352 959152 386252 911641 859639 685180 202770 729619 944492 301815 509201 862948 592057 943454 955750 754106 362177 693584 507562 656656 802844 216577 98991 761795 741059 513040 709793 538643 865785 975172 365165 947567 862653 376478 898772 283919 996603 352236 809667 350991 183583 391115 120360 176529 412814 386807 870447 732980 387328 10760 274243 340011 807013 631759 565356 474842 980361 966198 150024 959703 917793 204996 507596 485831 781579 879479 713029 387089 822647 307011 121644 263034 651286 40293 895868 551599 993405 885566 166320 631620 953735 34010 596003 308635 791726 175277 704952 542285 915073 344501 842938 92696 351746 546146 276617 898215 982923 345148 362484 769635 615991 674103 914861 407158 89367 427380 216729 919404 587259 689679 384164 256706 682606 569094 967473 35817 751333 698827 45361 444197 56980 923419 614359 745824 121663 454433 328988 304848 83034 853499 97985 386397 441341 117079 458934 78319 810108 544532 654341 632790 228030 230914 529343 397068 922018 871064 568239 710759 886220 231259 272062 929577 527312 518616 400953 603142 565836 441056 161233 737224 909040 167592 376533 303645 39926 659562 184387 36783 398215 996028 650998 295336 81076 404566 636878 154352 625279 653977 690508 292739 652646 108958 911258 441279 152176 753899 735397 201520 655137 939562 395577 792738 887634 46125 572592 287334 99160 470953 901535 325054 550587 362904 891997 835371 709461 119098 803065 795985 595237 811643 703036 573457 982855 523762 192710 466702 442286 444813 542572 328570 13881 638618 573130 117228 955025 686344 99379 31446 463879 167158 158007 355930 757371 98870 879485 206572 618529 143395 379123 344407 232928 824104 424241 423524 905244 466535 351901 604991 63804 598655
Output: 1337497652

Example 2:

Input: 1012 469 751124 795166 667185 510169 486720 893001 471217 141635 880975 707042 934558 632591 330688 563767 204674 75558 774702 402636 624218 677157 186683 295490 116240 64259 275481 970823 229509 161273 997188 203696 256139 465277 326088 831329 299338 304745 365391 396366 363927 130746 993351 658660 935617 776197 226753 570004 869166 231182 861066 970562 774240 326303 513494 138265 838218 510614 612826 781496 989791 986033 737168 436133 831766 933237 880109 324941 760557 462374 424200 267288 723773 368510 642323 708729 750625 936218 752521 963294 372907 915494 297433 609747 12104 822849 586731 244255 872282 805052 265386 532316 166729 989487 514006 964137 867318 508672 782224 553531 561975 728643 598895 211602 564571 741320 954580 436048 357344 769632 588403 696213 804450 249624 602348 409575 192187 128397 255648 640186 527266 243364 520715 462082 238947 288054 496571 41803 82623 780737 65479 352163 521140 170734 669771 393806 676690 113984 606655 889564 78787 472927 303380 463234 489881 289763 907861 207004 440807 336661 735056 95833 179492 118334 926555 679934 241765 611698 459987 683111 417006 237282 821583 750569 848966 600862 723634 960727 322511 624368 120163 728993 823762 884753 613512 74052 349546 698123 795612 376138 985291 124177 976133 827203 313488 648519 642538 732860 657029 125494 146604 572414 208538 953956 320186 234236 674297 684854 36508 979233 626926 349908 102649 28310 927049 423174 884262 892733 955739 713167 64600 882950 342676 813254 988270 661147 864715 124261 946040 987448 924657 673672 871832 220826 362151 67660 304068 543901 700237 771226 382956 183271 497414 553305 988500 404283 456732 52994 841480 319984 693403 89708 270690 608109 410788 895005 307375 674539 243134 273178 501360 485800 669562 734810 552667 571657 262111 102178 346481 558032 524135 45481 24549 77100 351984 107952 357662 91420 379987 622662 566369 923061 683512 558229 156538 715343 437487 368254 880847 344872 109627 536656 674388 314912 610846 102464 848600 395312 823996 910649 707292 583007 923563 390523 114679 984319 713112 435616 64641 133436 712894 878691 99905 343228 521894 819870 341112 172452 86832 790436 135200 350118 873883 573921 32486 160425 432518 664710 266372 264582 257841 16007 371340 442721 438518 906683 132094 474618 59758 896579 775746 704355 410278 387914 533937 389021 520986 488651 868860 124384 250559 36348 408427 814439 519642 107499 309308 79483 458618 49291 819366 722832 721951 203858 130292 175150 680839 423128 275150 544774 661734 379803 175983 371377 592021 37563 111727 705856 228530 795306 864709 104183 381738 936911 801873 21853 227106 773178 116889 168410 89208 687596 879371 706045 638491 464402 251485 187598 389051 509833 252599 260163 495160 303475 408401 241897 634465 47643 54075 437147 357855 887365 880783 489141 258012 642654 225884 498667 375207 466908 752411 418272 262295 235984 576765 130095 416496 155128 585885 762343 90267 32547 769535 82683 298886 187209 998016 579422 101278 780028 942827 557402 302072 243666 45632 996950 152037 374140 303778 664216 275524 858938 110263 830979 545102 203158 593405 987932 952174 554693 366524 265452 130676 373032 280681 1157 649594 969374 708916 320615 331994 331314 504213 566422 485811 298235 823760 222092 96854 588326 629074 724126 520725 696412 626164 384088 14503 146070 62621 130250 753348 787911 863530 563787 40509 496822 24754 426955 631553 642489 996741 802002 903148 129914 414879 300091 535400 286568 605616 267700 685671 740259 870210 758441 451825 108607 941577 283031 400594 340709 978109 910026 274060 881683 976221 71237 599093 971770 524105 810953 487291 90962 956964 862159 567456 720186 339895 635977 438137 329602 417066 561951 381064 792515 712444 657886 124025 625221 497262 148236 276057 595033 518876 322840 838251 36565 780711 825029 570095 507072 755125 844815 283959 658016 33059 515913 27285 469930 59940 511105 896246 967570 394849 832391 288598 655381 167771 429321 304466 922189 887718 490172 910653 9534 344619 62725 725832 254841 857834 198125 46098 872486 8612 232489 61393 920143 577938 154978 52663 656524 711840 752364 388597 437856 738067 285296 291675 160661 920141 328930 257623 779600 446692 227321 831457 68546 591524 129478 415739 574792 143445 342473 664575 653927 657991 466205 101550 267411 850250 986441 965879 90470 873133 454268 637422 622321 912628 26963 116065 244044 348598 136406 340342 808698 575698 94354 605871 818643 848426 619751 574563 100062 604618 457795 746098 5159 599088 499660 585815 497398 92200 817109 461469 983065 896336 209760 282752 36847 474326 299321 336802 117925 739185 57594 957905 887419 964467 663154 258810 839946 565343 436571 891342 468256 270625 68396 446172 896315 865497 406432 601705 706248 509336 153542 23556 134517 436225 691436 184577 437555 768609 731159 885111 801741 628386 342987 578825 539100 555032 95519 900413 873882 689969 356380 228293 971514 52335 940431 998974 361614 885259 942562 904249 805032 284151 892230 838387 803002 642259 828080 765733 612063 380085 356565 457107 427218 848697 358671 837155 674988 108423 614041 716777 944195 696996 167716 451411 196181 31602 779320 544133 12743 686104 792238 235615 941284 527427 353727 835106 430284 721707 175749 529229 168451 292753 832397 218763 348877 587984 25174 660955 375298 601717 128579 792748 470976 270095 123164 366148 91556 225903 111921 212564 56140 572465 599074 327609 471730 522495 612628 793708 653350 70723 928701 230053 118145 175541 329840 573335 108749 517229 171333 240681 346982 266376 299891 520783 284915 896432 515765 211616 425603 450186 790031 320279 167251 307190 765834 851300 783215 509006 970321 876999 240817 786068 816983 436748 842432 195359 406364 214911 341706 10187 598962 753645 781767 64726 535295 450020 495154 431431 263359 838359 186870 389898 524977 237557 13644 537180 932344 645872 522343 500179 399448 697215 701197 815249 801649 793061 189784 659342 839538 300933 536195 36935 442337 895098 123298 574532 216510 944413 836333 962234 68684 759923 988798 497039 462704 334494 659658 285259 768997 127447 642644 213725 131547 413364 470340 232186 725173 301321 581070 936803 667576 196444 238812 978146 396334 183241 881562 51074 267267 821886 352180 395648 343313 812038 94695 87502 470225 780673 702835 973431 534894 364147 499022 80996 712408 536361 627316 302238 596944 455005 584003 448168 851500 45282 332963 242431 186807 73544 686928 970324 658031 270168 730211 3408 391972 123043 697389 959295 353435 918542 591461 470156 119100 451572 992711 116550 166749 742910 289507 155846 126428 72100 930340 360237 457825 287191 475963 656557 797852 428207 60243 853052 877061 28299 870683 431490 100591 53595 499968 115556 837761 53931 956501 247017 847716 863400 77107 468779 893161 994224 225251 318779 386982 960219 26216 595534 841884 875111 68839 432018 393776 586819 604568 929459 834369 500794 881930 972340 634232 372886 907780 441462 720396 659902 192269 770821 638747 471186 124090 95397 860693 166507 441814 365107 871518 111991 18128 981662 677085 508520 866063
Output: 235180725

Example 3:

Input: 2309 1427 466617 898842 839955 835795 655301 581152 486873 54446 355526 932628 135484 166382 759108 286537 880145 286860 15657 567808 628439 151859 122755 906732 623755 755244 544736 216822 891450 253771 658812 292351 497314 651495 744699 188976 761316 660480 934056 115767 500861 51596 349902 273637 35919 870412 417620 143393 899615 534942 997508 991434 383976 454082 375352 997903 533748 901982 150657 296028 144507 771687 960819 532347 160599 505321 446950 238469 948282 455408 478657 362056 161955 298699 506037 7084 409785 834246 747238 347547 332148 505926 869799 395180 683786 117659 410286 911289 32888 777714 445174 443229 1547 770603 198048 410843 25956 942200 927383 935374 795746 762697 754681 806303 351446 476844 244333 58248 162817 855499 252008 99322 509211 103513 656319 813022 173052 924037 880803 871432 834708 716647 51756 411399 834331 247958 804673 333319 315435 983445 472791 437452 605908 112859 898557 725479 338517 53535 672105 899380 50137 470187 537018 410 722927 87002 648813 61323 829222 804335 364409 507616 919333 245735 233314 904717 30947 973543 568617 416075 665237 601664 860689 888555 982709 479880 322982 157321 445020 684588 93339 311451 745816 920386 57537 545672 382463 714462 546453 741876 351086 961723 963906 38415 961053 447252 531395 989525 499556 938635 913282 505433 312053 187496 214288 985844 316863 727551 467670 838312 768420 851114 497126 448166 541037 198200 655925 518675 225944 894250 743346 475800 509037 224598 427806 525755 27008 166131 250466 352829 824725 861965 400912 579536 690773 70724 259321 830124 664973 289564 582525 407346 247588 217967 84861 261971 359476 375629 805034 567100 847407 799268 960967 558540 366574 190900 704081 368860 838083 876193 310010 185769 463386 961124 257140 325254 256785 679552 404725 566546 889634 974083 9489 732153 361297 792089 82515 873 893534 579184 724905 249344 279849 888537 886887 582883 525801 462183 917250 204085 321958 704880 90290 917695 491130 927305 495092 85300 155049 967225 895388 715875 715510 413822 197708 815047 861946 408745 638587 971892 408338 692794 409029 941717 100307 420938 140435 335687 341252 994049 488240 968790 277981 540828 276651 173599 778363 905019 505896 893992 756649 430396 838325 617146 300410 295819 471119 598859 485190 837962 71215 501 513986 308407 907003 572920 306860 764801 411911 850331 737788 387537 168587 862119 163201 235606 990324 568930 285298 720819 666355 978264 475250 539997 912219 180206 658987 834242 695540 845182 19705 791023 738541 591959 12557 109018 340568 344209 145617 227326 458395 232453 243955 620180 179431 674070 14384 713715 310935 459445 214561 996386 89028 965231 178261 7038 508361 12793 536659 417198 808680 966530 50142 784504 430362 66643 156465 736367 382167 237586 852676 114355 548085 407606 243113 890980 936660 789753 61512 714145 422224 974851 230239 767108 76001 905463 892014 81960 113234 435717 125067 712499 568104 393508 271548 836612 638357 294294 893974 960768 112900 380690 85196 264364 780914 587397 9744 886414 9244 840739 567579 352199 91344 15658 699562 760432 348268 726920 623325 440978 272394 27833 822722 224633 175276 788284 393637 295541 510240 521986 82995 185524 578657 547365 729297 186465 314746 468404 826367 440747 804422 640767 804205 310234 158928 779155 303691 238705 11479 784089 656803 418085 205415 484644 927270 532771 232799 381609 835506 146564 188782 359186 418479 187429 312583 955123 603552 133850 653607 295582 52542 989740 908719 511131 584988 956116 47667 286508 907776 179220 260443 481626 234145 323074 950347 705731 865998 68158 491615 812136 294387 54284 321586 383494 579779 380209 711302 48062 465520 392798 391505 101765 876747 848773 617109 833388 789287 628980 927372 397699 417019 855732 656570 949761 205276 114898 479477 450001 384015 526331 503660 271286 519486 341144 665157 42445 202505 149443 141313 743280 414543 838106 715005 995563 255642 362059 812629 55956 347174 187014 836334 137586 926327 608791 133340 760875 341057 932862 920963 390864 183522 921385 839124 846715 243556 214059 385671 24494 179902 459124 896673 456241 172390 662845 817537 777052 318355 457131 488200 613746 835880 557616 917926 472570 630946 342471 508022 469266 939999 935747 374544 427102 134108 49389 815153 133341 880232 142195 909354 513162 971633 243455 933560 982693 207391 892812 471113 970348 857318 771045 306791 109211 381085 860892 52613 29118 644644 43190 427087 528701 674505 472019 412919 741963 156097 868140 430734 136591 446654 187600 935930 940669 194672 800778 917051 805361 31617 730028 581935 399097 139960 42048 359230 718054 707635 695486 925603 473185 519534 751697 272060 291081 953 973141 184615 918579 492608 282394 135618 230001 402809 106485 142593 159320 877055 989129 988139 294353 978080 50658 295653 1515 490899 363167 843167 644584 78658 809837 542425 495031 25980 946003 74050 348740 419578 740789 19129 222793 117831 739190 329503 187592 378163 940248 413589 599826 777533 758334 12624 634898 590282 320041 113338 647097 457042 452128 952245 476062 447664 6504 628433 746290 360961 349803 138787 791058 892451 833603 459814 924421 850769 537795 416958 154418 723325 82893 91283 365880 355793 303635 947552 549968 318938 51694 858454 971629 375974 853329 319405 8938 970180 561987 920885 454434 942888 227146 651171 752956 606001 306550 566416 117182 644519 763181 157222 994780 933033 868359 438771 392864 581242 186996 790283 947568 976465 575712 728805 698647 852573 140494 670446 971391 275830 135014 987664 981655 969834 222747 74646 827445 949870 658433 881687 121198 801881 455353 742115 163541 176829 657331 687639 866854 388901 445943 238691 718692 979970 124277 741688 47815 979811 27971 134812 616192 108911 627679 248158 77380 266107 546570 187832 738046 362304 760741 438168 178129 391852 332420 924239 993892 786414 778308 203704 286996 23903 978704 90967 81071 364152 790942 592511 165093 85110 21333 222306 432224 866454 316413 956371 589228 632696 798985 604039 998477 773129 439865 160026 866227 376764 491054 816485 749711 297687 281873 184008 703723 844926 392730 987704 414273 311368 871177 856578 106864 819296 88574 394093 254388 254193 338148 1632 80344 484361 814144 856989 237718 34976 718199 654355 734516 835615 636310 315851 534032 113378 966007 913077 36611 892386 991462 933375 589574 690774 698032 57726 493602 168841 169228 641945 305898 864346 329156 637712 966048 842464 863433 679655 869883 799701 5248 994837 413535 910641 424608 918054 227616 495063 960140 728589 461579 701425 115546 429606 878450 915098 632058 62344 844130 75010 820431 135771 971273 949512 759809 872327 737175 769323 133741 296075 440276 185783 97867 910852 478710 121221 59328 128095 622830 330659 482301 678677 787571 751673 877593 735771 532101 149947 613744 887178 768905 167693 919873 169942 265211 586095 126960 591064 337203 287388 627457 987353 339065 785979 171978 633503 74906 126422 60583 984208 356533 988446 149826 270555 134500 126767 182934 504985 382572 819953 29406 677748 651507 949942 242928 437898 592483 144881 282704 894382 936596 783512 338483 131380 549210 380662 403986 819363 118304 913835 315901 882952 516244 591396 99660 947298 845626 79679 230826 722188 44373 278064 397473 942282 842865 193885 791223 65906 891482 823684 791360 577958 961361 934078 201578 408649 936795 421153 537088 135791 592046 956919 356157 332226 396813 384916 71812 837533 487547 260445 585333 585652 480530 452064 536857 455113 782124 88573 657932 592272 787419 290445 134401 693449 125466 101877 848678 173405 940479 236951 674726 97357 32959 553510 797870 750369 355847 514805 166387 498708 628996 599137 922627 164580 113962 647346 441594 672163 140429 816659 872041 556839 998637 212869 70762 996279 854159 884069 482294 254047 102088 439313 38000 991144 690927 427775 872372 490861 425187 774091 153742 526719 159455 417268 193474 953904 848309 199430 422992 66127 821952 918637 530120 387549 224586 556410 569997 425186 439570 478166 117080 161573 290320 725658 629479 463886 310859 105440 104469 175423 443838 527181 993949 996369 85953 994937 574144 704391 483272 943506 959706 496740 748519 415105 836236 534261 34447 967374 464207 455817 662106 604450 927236 14942 642769 84235 729897 882620 382327 248647 596803 691785 208934 404566 144392 940913 192630 957113 227886 712229 345752 186996 502367 381940 633844 62527 478320 712386 290657 199837 158034 33777 177017 744035 746587 149695 864960 322005 635235 239948 123074 370601 315189 573856 872113 64768 78522 81480 816300 953039 480869 904575 890664 350561 790366 300819 90042 348147 478595 443145 648393 920864 982697 256032 400988 462422 345294 882585 85070 349648 512932 858491 66353 483518 334023 575421 663390 790949 897677 812532 649076 218948 195560 15363 270612 589320 55958 409694 271148 608792 584970 205760 918525 534578 940347 203492 793272 577269 261248 276862 624031 320810 785857 476387 25827 738607 893523 441278 908039 218288 39747 709824 283279 269748 144424 610378 599500 28441 640349 582662 846951 52393 442457 816194 550569 449439 767484 753511 1525 244922 605187 131827 309884 1073 983373 744290 506024 515408 101557 102725 589383 935557 238943 228507 731368 825137 179625 600402 587496 785432 524055 253737 938669 367412 647751 763937 856298 912061 558286 719991 434389 3520 504609 732972 727483 517615 797815 707582 300443 884386 700524 445883 578990 262281 973329 814031 755827 951574 428845 795898 376726 551863 304359 908554 842247 448897 888099 192251 285761 681415 593022 31496 867099 359751 580206 826572 6906 108063 927809 620787 583017 814966 938983 782835 828493 573475 977254 734928 993454 974212 842668 74048 949895 689253 141627 388668 355833 689901 811330 319097 282564 568047 191184 162521 854413 641027 558151 826232 444928 942516 331633 679604 809710 883669 701742 412489 303107 67349 223973 931658 782645 572167 190719 606183 564581 357166 754757 672292 968927 239789 440549 388379 219906 212096 824316 401907 31280 421959 375447 367942 647593 975744 570856 805459 231565 299680 201060 734845 162697 442910 780523 577315 124033 205406 938782 466754 173938 693673 537622 992179 21457 475884 840598 101722 927690 836162 660026 341343 663690 287988 456601 538348 485734 628737 833311 533270 411647 26635 901041 274981 216435 964550 39621 374814 710002 325081 740239 230592 262948 26579 422343 979482 710140 933673 635436 24493 969937 745395 16564 678789 119845 498712 873015 190221 494260 389415 995137 37650 171452 401063 198022 685664 60072 489478 744417 321436 722492 66131 69489 426353 431564 759716 119113 138451 436339 100313 361859 66450 749670 960361 824427 634408 288519 21613 921771 418758 120749 958809 857623 506061 708914 777034 399959 918680 95647 282704 197835 104630 950553 620664 908563 877298 346086 346668 733424 909853 85238 826600 375738 965338 427015 172909 80627 561500 319494 12866 870539 747771 379143 641936 467528 309987 368913 582191 25311 6323 610205 862106 44647 998379 429229 251341 313805 83777 461594 219392 812512 374152 831077 79482 740205 986462 384304 555088 599525 831992 955597 226487 158725 283235 161961 171183 776448 437696 598928 997841 318052 797903 682895 467866 300902 391858 933339 916219 685060 937157 42543 863198 761141 156801 958370 521479 4511 457901 534350 543244 881816 550084 614866 873282 769918 454672 235065 946907 703622 460743 317228 25139 901294 173416 707021 482681 801563 916148 617025 453000 280936 132944 187367 418510 947329 250006 839544 514848 403698 600775 978655 172038 43694 576571 746550 631958 307085 338968 835192 747589 950058 765472 775465 427702 133897 299703 697097 702837 935662 126993 592368 172133 702816 462106 191180 115205 67235 376922 851437 720650 347524 127913 195481 61499 45209 170194 555961 982433 124514 572984 972664 210094 555772 181191 48618 790313 418052 489499 331223 205360 798628 939920 536618 931540 981912 264491 922423 133479 331692 173520 574548 60765 738981 46804 576708 506322 338939 313624 927387 644860 560372 307424 9014 125169 511260 201721 701007 387952 474319 611037 379616 265190 829767 408297 858176 236132 71173 115647 320706 535924 419263 537096 666694 310708 334171 469363 426014 12883 818995 662730 722645 295266 930305 45196 299165 977053 287458 137438 242622 431870 94028 743503 743093 548504 177608 175438 768465 486848 880025 907054 338227 649453 276474 860562 288749 458804 217922 422201 109135 900139 189788 718908 613727 492263 140336 301220 481139 957193 694879 24146 540603 191418 108736 542446 269028 345934 7002 995938 581964 254609 877154 586767 853584 179304 674307 684356 695362 85285 923601 273946 373407 62236 754675 708462 591789 789747 266817 702898 19859 843642 706766 81203 990491 620224 198072 884269 768350 846823 514986 658986 565629 227844 917477 626407 220708 350120 178999 636844 125039 108881 922572 48230 308314 21 976873 578438 275238 22338 424216 31776 643499 407534 905576 502197 694973 592297 673822 89908 326128 902447 400203 362386 843560 816919 18426 593579 39630 592420 290019 604998 952226 745859 191121 957207 836894 648540 669038 386090 155606 394206 294884 988597 719250 221179 830270 33181 758438 206110 200247 547838 658762 33075 124661 472560 320233 7717 24286 531574 503701 332246 202574 894568 382876 984303 839123 56917 918791 812619 816131 333577 636071 898126 691494 198323 889582 245266 66221 694909 349331 645777 641113 970985 147959 531923 790816 126816 696277 735690 116656 430489 999647 379259 822072 607458 23515 62298 651349 68258 547397 157717 48763 967326 717891 651140 376908 420862 645400 150668 979002 620912 37548 43841 488261 975521 202821 371547 892654 16384 381544 782787 704286 631666 21971 122357 870624 194497 655250 661315 13771 215908 849369 319881 131566 840257 981558 763104 276360 906607 3111 16249 291298 602387 78843 983295 546318 76872 177163 377070 173130 220579 155416 816564 476066 12103 393273 322302 84753 309509 292038 410487 965251 299299 723263 291321 869287 586082 40050 284874 483790 29854 57554 15826 660392 209339 917526 724200 280438 8924 590468 289678 870646 998833 776411 214405 452634 759488 814107 200135 276192 226668 152605 474515 77619 404017 800623 846610 217174 67628 846328 859091 991047 391433 878557 692159 375770 991177 585543 741384 504969 230764 372210 247981 111613 817385 544516 90634 165758 755355 867326 547201 189103 644793 421556 247850 940605 987407 695904 172848 855750 413942 433249 868257 87965 697527 534903 824963 672439 239131 661210 458746 490894 509247 262083 956719 14513 353505 115608 700978 428999 913428 971882 796186 413744 741784 856957 467439 482730 278085 453193 807833 863473 963902 659971 355920 240922 270443 764940 620927 921433 50750 780520 999430 948596 410166 257720 368571 899339 807374 42307 126208 391579 287317 170857 340587 173989 431855 41890 845266 544511 147305 520292 665617 580826 72610 521209 504192 978438 800849 468390 730214 282175 348036 117688 852879 730546 827259 104595 624370 612160 91368 783902 190389 830524 326654 922009 838533 369467 378209 714207 710952 564674 257034 835966 843604 704413 22589 507953 553287 915891 961152 93289 309398 553739 557156 27605 309223 474487 772519 170080 336772 521107 586842 97228 198218 324692 427246 478527 390497 712367 403887 205669 924890 190530 657733 134997 703429 645756 237153 322056 393834 683606 685477 154842 228507 74472 532800 869406 38414 571294 99282 54325 992439 787441 53582 238360 661325 51058 544933 677224 498057 98418 312130 613412 498824 646209 85238 323848 933753 626697 489902 58215 423131 401797 976678 600518 181594 743720 317259 935339 124806 985423 40638 923031 366008 940465 958342 738284 828260 539124 118287 649917 666119 190875 554241 336641 266241 691907 497583 234658 66178 282246 211708 678262 31133 469822 121586 944542 185219 547834 940658 360369 53976 63592 323744 525660 867568 666368 362949 59687 549397 400908 84136 183241 744149 185355 377795 645152 255933 386116 358646 502696 115126 306383 446060 721257 532520 477610 455769 183095 92051 799485 690510 813943 155023 295102 223644
Output: 731442153

Constraints:

1 <= k <= n <= 3208; 0 <= a[i] <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.