Increasing Speed Limits

Problem Number: 
23
Type of Problem: 
Single Output Problem
Problem Category: 
Round 1C
Input: 
Random Input
Critical Input
0
Critical Input: 
20 500000 1 34044397 942475857 285290546 233459890 262143 27 778531071 478442808 548374783 308073206 83422893 212000218 478716954 253195088 177976935 150684103 238705282 544118711 266035281 107502784 368192145 476184022 262948728 76122559 216654622 248475547 25676357 411398449 118850100 280155516 284831197 321535605 153133880 134913011 267278025 36352599 262143 1 0 1 446980011 0 95964 90 599045317 521316857 727089494 290089318 312709453 318873673 206389249 298028848 45794809 475695467 496694758 662152558 528255614 138050462 391261785 222223066 425763213 503959729 722811667 19005510 239331005 499008944 338100050 69765755 113140862 609893627 271206651 343145408 644739489 621314226 215101232 18572699 655099060 203891367 308662017 274503853 522765040 515051266 572532702 602344683 297442073 342137966 571192582 98608194 480188428 235364873 354616094 212646981 46019942 350338267 231652491 319135781 156042552 603537376 422686371 269183414 520126343 588362 612328822 437776338 621902588 134125394 456349038 583696988 371801595 71706395 131111348 201261976 586757662 703644050 76517165 190895075 352477356 681494581 289503269 139361124 223554794 644119363 352008105 269574736 301152971 583660596 622495352 457195523 493893312 318092229 33074277 286930162 318680591 679187933 31401840 247278519 120008668 209415 75 681018507 488493941 54816370 35221126 31301077 25741497 11472710 13837473 14068441 37078898 24665859 40453086 16158757 5896484 7590240 51354068 42027820 30722718 33613077 17544696 34095507 29152294 39519354 3779894 39382207 41635262 34263968 2281152 8185998 7427527 25503219 3332609 7427527 31250125 38553735 38728604 47346404 40381227 42920859 51769627 22643755 3125130 37406344 29157295 9021615 35351366 25694993 41404217 1612496 49662853 49303696 26062785 23998777 34006680 29842680 8564615 20825572 9290278 1200549 29011570 16717806 17058551 22698961 24145333 48308676 6436326 53228719 31193493 37172335 41333208 28146750 4999721 34813121 1091506 24511798 43834736 26797654 50206791 56990 24 171921134 124737550 128075335 52938691 95269194 37069078 100712551 112631186 11875657 109491415 112297490 49684604 81724473 66428698 28410232 12634001 50275787 32289483 94125522 98889045 69461819 53065962 107570370 83770332 14620118 9360759 126213310 262145 42 145531645 885757306 980606547 378455658 814110217 92168997 71118287 467083865 775438487 880685736 623217802 595151384 245416213 56255840 928449257 481966308 116781280 151291508 112650517 199565913 449054739 240771283 788274512 82119736 220341932 533884977 4037547 663725960 55068056 10343988 828651059 773948262 804679980 907347701 171797373 451913096 813246144 56645106 918996961 421807531 751060288 375337662 36352368 15869954 431593502 262145 21 517390101 629185474 254942425 230249956 182707522 177726730 221463314 16736152 154446216 135047575 3521732 60310147 79330078 237567338 5162288 44025962 187289455 231267760 17013746 161170428 52813100 104842228 12221209 48280558 262145 1 0 106857578 106857580 106857579 1 1 500919862 638803977 672251447 520731691 262144 8 344132383 951709009 722466051 523911460 207973982 668055032 261297330 137925291 158202281 350899081 654301879 262144 44 461818864 146611969 133102166 87310916 48654929 105742901 33619206 67577923 31598751 49318271 70128239 59274917 81081458 74578222 26277692 22973943 85405865 17196442 122492519 99609318 25023807 1482304 99440498 86873349 18226296 51718971 106905063 36003260 68758783 8272623 15849307 82268586 76557460 42694156 18628344 107363398 130588066 34398559 23990163 29084651 83716830 94118402 70510576 13847130 17745467 96788268 18972081 32120 38 597181980 953629629 571089127 410173084 59861848 427637726 124581572 213470673 289018355 490843185 256663175 170119558 132154487 133693740 423789105 314348443 284431223 31067954 275228980 422543211 409320777 536066658 136017385 413296126 86548672 241219003 273071525 415531233 393566859 14149952 7407819 199712841 14149951 470150835 175669658 74011799 326699435 300251231 287482472 181501523 356878149 100 100 0 0 1000000 36806 36806 37390 37390 74964 74964 76131 76131 105103 105103 129640 129640 151741 151741 211339 211339 237004 237004 263047 263047 293761 293761 301435 301435 323326 323326 338242 338242 347077 347077 349319 349319 368336 368336 376122 376122 378338 378338 412918 412918 413843 413843 434061 434061 443495 443495 445927 445927 461547 461547 501026 501026 510648 510648 518021 518021 527590 527590 535780 535780 536963 536963 690313 690313 693724 693724 724943 724943 752202 752202 773335 773335 775740 775740 806536 806536 819618 819618 820864 820864 821601 821601 855530 855530 872860 872860 901942 901942 924805 924805 935327 935327 936176 936176 956905 956905 970043 970043 976754 976754 500000 85 833479489 693361710 738690593 241004332 111840552 532707497 43824357 125475216 644348871 738468855 15118950 162849998 540459550 26376625 566653687 66759354 455119920 305820340 307224918 241732259 734933765 464317248 592352013 268392939 274382326 383400897 268982709 81254232 668622103 421056956 505940667 214500166 12263901 7492504 524092629 192692584 540200001 567916987 318167801 445858279 636283380 401874882 677296408 506640468 428251508 505259502 641987954 213268966 140977380 279110410 455001225 137220552 73325196 308662645 405613491 347707523 21961080 4493738 497549886 20480721 494138826 264799961 234980887 574990858 272292465 88971055 28992849 73801873 656888042 415748781 588248283 623068960 78933071 526854098 459606967 507184579 362011138 362904328 720453545 502988519 642014738 505352308 708797202 715339935 143912491 444308232 392944996 165873571 401585 98 580810038 45401427 869224038 472428710 368440569 785110130 277783694 43990480 260018475 360268665 488196920 541879011 475144554 862843394 340710005 33890338 131544648 665584779 238031432 230052968 830405139 311283252 515343513 489720629 420998116 277815300 259300568 354801486 421629574 846275544 657351916 319547355 568015933 404819665 791976066 527420930 780894223 660724188 162375839 631877127 611957282 650572759 304532100 217877798 235156544 236206533 251768136 366701192 32567274 80763997 596754160 453936841 392047249 242873635 74433433 404009793 111653363 333734001 349775708 124247365 770973973 137903586 443794720 469765869 133687679 366546748 127962761 45357864 618235365 290338600 268199419 360968609 531875788 572731519 169810835 767032332 808938053 421578971 724697952 432469755 502342968 43192502 17182559 485354645 286066137 91615992 20140401 857907966 16314421 369916109 112931293 378252823 98784123 147690441 848018692 692660268 105201618 566945881 328982560 723436983 448248910 26220 69 214840371 558065001 491810264 268782196 201261975 452910276 224084948 76284745 151995087 84752040 265969062 240003961 43870572 489523857 190818664 395878677 65793933 235440601 286234613 196479021 491141728 288317662 77797624 267684971 318716790 139947181 274820049 350118630 130694667 394828717 401095883 33086285 394828716 31969267 301868481 104280428 484879543 345710837 180565173 145064366 250220285 266291643 385068327 294090857 264005236 84076728 198159270 329799170 139274737 484393883 346035599 138606202 100658689 423833224 226048581 239132887 71970141 9058366 97441254 22422216 403887083 318294545 367076173 126662944 350263812 488702062 50700780 343333091 162360043 231265953 308154865 412580328 500000 41 627487402 850757472 355347209 195149906 73848167 251412231 230473233 222197486 323778966 288852813 23031090 214561397 185224104 346800408 48013925 263605687 14607016 284834790 103415800 197949405 232486887 23721250 158845626 285143584 256969411 89625025 90825289 159132850 78786138 236550095 60525440 203448798 170508467 352696762 43251496 228956240 233361390 258324335 80406123 201793148 191829939 88036819 61007336 6306441 262143 76 169673650 358307488 976790025 342459430 495771109 893272552 18064856 750713533 496008424 309353639 570534382 673735155 828739054 479326287 210352273 557920281 374903771 162718172 637250360 461547186 932707736 573332074 31007543 801088823 633325495 702062821 957920426 332301375 606339783 643314311 501975026 11067222 472620688 877857476 159623055 968391797 600436405 177687911 548411707 902541232 293137952 925042491 405582764 145086981 233675155 615935037 509103665 608578927 584749611 169564000 93336088 346763724 742896074 124343632 171062523 205527947 632502855 935079351 537829322 262052613 601603637 63014323 79216238 97434300 746968202 238839293 871922499 176710984 222623606 249640583 102462191 515761558 3989452 314141357 466944942 237664607 930076394 976048607 846243534 372914 73 652812536 169882417 338406909 147136321 303777868 73993541 337532301 234534584 223115906 37996798 275942672 218969514 131466164 233109637 124556735 48678159 228315238 152966967 173365446 324410121 297309737 148797586 94274210 140417933 48384212 313897866 162347120 154642522 169779288 261505240 130641241 324440980 129242318 146298174 133170392 315977992 103249521 15253590 95063473 209323233 53250389 32599236 311250554 184716553 148666680 97400380 116352519 38575009 133325153 289717965 24578221 92227981 321473358 1810237 115603720 31450661 198665909 277950840 69050989 30038289 84006977 82650036 16072360 213249296 228948210 32200558 190820379 215155538 47454149 285883853 307436577 322069253 201440895 280280222 51336703 11700666
Random Input: 
20 1000 90 119183605 800390554 869262611 37245610 727819161 786210092 249057005 53022121 620417987 308912558 474169225 293365291 614383450 183563293 241581016 711677169 165041385 457172424 89386931 189354668 368449252 476996647 598101336 612565645 836802951 180974856 479547342 408040952 395385160 844494841 379740911 48292067 844494840 842822800 545841862 294092964 350811855 794898867 347115085 101967231 234548814 412325884 855636707 439973838 186930751 227955113 282388396 351972136 276169111 832079512 132368378 644618363 30855123 730469715 387921397 867658074 42181960 458510313 406436415 28608694 433742544 377218900 76900761 16347 811083274 622742623 294109312 292632518 139420453 232265971 854903935 834273452 644591856 432319605 404984679 831522607 660274718 278414649 314232133 67181218 241231551 446600511 302841155 272086674 307807615 281804126 270482137 810293760 740314440 267960126 838902454 304794373 236220600 1000 33 965205667 724223372 169374881 149880795 141176592 110231960 21914970 65228061 60094288 129111051 154094256 80916751 16599472 70551180 63825024 5277308 26867338 109836392 45363145 35772408 111152952 104976553 15777395 58254500 167814198 18708534 90518765 27073586 82161051 59802062 145404848 13899824 43552775 105854414 163780619 69744292 511 78 869187222 480490764 414973471 411933029 65761477 349539367 380766166 372369781 226641639 290713634 370984670 40055529 84809113 45184497 211031986 67228192 402689911 246458000 242089240 36046246 1836279 60600466 379536075 367943349 288705299 310239102 47898545 397515148 238555507 360281099 21781957 231456507 42744392 217154741 228416065 108505870 151720638 121592467 65902180 378362277 412306101 21913379 3444335 9525451 409455054 141860028 76753643 397171494 315701735 246226590 18244270 317538014 306827056 325164052 197891599 107942591 147813390 173173851 90484269 313752604 118481479 39649933 130235641 161225872 256804675 286035413 269731742 335909020 407627881 335633922 226681533 332344218 284931008 157509575 269253376 279412591 299369603 346007020 188994322 127481574 104643846 1000 17 651165168 999463789 141914966 109788020 23556100 120693253 109077781 2480154 97633857 141096439 39198570 127238684 127170638 46355679 99602049 31160 1448344 87690226 125076824 54628000 902 79 700521650 713080455 927846731 409268985 774510410 825098871 269882313 235667782 674695564 533957295 231036614 191878087 209591875 467155519 178188650 669501779 708370202 340497539 653095173 256959682 731474587 241741979 173082238 665275375 820985911 814083218 49701607 915071560 409621033 315759618 687746479 194854757 96122701 438563909 312333556 870633111 44025863 290425683 814510707 426931241 824382979 117700590 618809328 742184668 293065924 796997978 192049530 73589395 209648787 845144704 38758891 649333188 795096497 211841129 386761833 688235677 98077616 144673254 383670321 215908463 168642687 143570069 118973034 264765388 290343793 139516405 843608313 42579470 429942088 438482103 469510712 326478336 264392507 160473309 140816273 557458431 29624557 41075618 339257640 875329889 886220322 378016531 634 25 305026160 681316818 517704392 114506795 288583038 26966670 498177116 320263368 195609357 349957000 331674350 352812692 456072660 471190755 84346141 498652130 383428451 5123852 450458450 7974263 269516359 503369707 374704742 125042266 241204078 415780360 356737853 414601442 587 92 610773785 531223811 251091542 23345104 1862530 99984894 208424295 104327414 213005317 119928299 160550835 82629363 239036858 41813700 138995952 69818134 148857639 7568940 100602638 61013742 96713140 16399105 77086877 57547683 215243383 132311547 88963438 77609832 29734369 82373809 186200533 166749159 82373808 127926760 190094263 196576568 89160343 147427017 49812441 51074118 128604004 71611964 133703481 116549320 113425664 133948121 47616142 123531991 141517061 148218780 45794421 99478889 164617885 235221528 18275260 241109956 116441534 219578929 67628247 146175903 50861196 115077468 174173751 245575234 104252917 113176472 191060260 193413260 121852177 240872701 244487378 250456181 61393124 239439547 228254189 36067476 234636356 24778789 159599468 125061875 172997569 205393889 85789452 198864143 189523876 104064713 188882557 54873868 72552100 117759492 62298459 235753526 94085649 236472210 230237218 511 11 849519555 340732733 841257835 334598371 57591353 592907002 196122082 402917136 26995629 55123782 400561755 387799554 319349158 38143934 1 1 4712031 479056446 733904406 480159960 511 1 0 1 672941413 0 513 1 0 688898794 688898796 688898795 149 91 573145152 870824527 481004729 75075055 208150980 29626331 216990020 254414677 454639588 327201256 324953468 82712640 366182083 317173032 402224719 405380653 283737592 190305594 259666905 130905013 479272055 181990891 218595239 265259116 296984091 223307270 77836644 68879038 277677638 329891552 456550001 1018518 144417362 191182005 76093574 129103610 220808336 69618862 160053556 451983192 173355386 4002295 311231101 58532741 321175328 232451091 240448662 123908191 199291953 19110838 31348473 197559280 458641726 249943712 239353664 274621089 249786251 317190309 120035395 46459160 166077132 95580668 47477679 87029762 63297941 381111250 216133373 284106277 450730112 376186929 31620009 143080770 380189224 342851110 459153508 477899820 351837469 218597441 378343280 70124693 14243548 409691753 44219241 472885274 436170733 283572906 43036902 204952255 119758486 163072298 27946684 62370886 258652966 332964360 513 13 785065825 765114905 916566486 95353856 883674091 305137504 13269152 460356989 825060280 657861008 892676595 266174598 572817129 274730276 230238572 525394711 512 36 549595770 202350236 71364788 56274617 31823730 22214675 2138847 11297440 37292871 3069760 4761595 63193202 53285073 7826135 50554206 62736672 51735995 41957111 53510406 64323164 42656399 20011740 7738375 13235366 25928931 33612578 14382198 45763163 50083593 47661257 24440629 32692426 42907184 68002004 17602255 3366126 12311884 13201095 8123559 513 68 270476179 256334679 189362159 44861932 114119699 12775622 155825765 184670879 146039137 150592453 131589105 91439240 100957800 92350993 102655802 150911111 182505471 140923024 49414039 86228930 106980056 81426217 73392183 126807562 131833268 27330173 179836995 162677162 156074828 25183164 54429023 86874395 25183163 6275173 67236429 74802963 19050795 33700035 70111683 100590034 184292488 137200889 2667115 31388231 40189723 40823019 117799443 33333036 117246144 102713583 55062067 34864042 184139801 128454250 161671604 126610910 91284525 87646541 35426014 57997194 48329806 89855037 80371691 73512969 96130210 147608120 148315932 50681107 181308155 153927716 151271141 740 10 111410106 764965093 676085069 668516841 70175581 518256219 505056510 665876688 193975982 533598839 615641075 476795463 209351239 512 63 687946481 929689830 8989182 7139111 4177606 5792168 8717741 3163992 7442890 3076908 8923007 5553143 8732496 5442847 586117 4279761 7718313 8981673 6956026 727768 6118238 2851743 8077028 4522184 2879826 276536 5834659 6614040 1279051 5227442 3324357 6013985 1570705 4836555 4163914 6679161 1639541 4823323 853972 1024099 8831081 787797 6577243 8574396 7161494 7163360 4795825 5890625 8086701 2762669 6618393 5215757 6545262 5706239 748760 1366756 5982775 7514269 8911646 8192676 3752529 3246822 6148329 6254084 8083377 1323061 414 13 477374730 943547914 549578845 190966889 213936630 62542532 131964255 123032824 135658062 384907847 433813287 430573864 57345548 301314756 481123109 168234636 428 46 819705073 68230643 755036387 438451387 472151076 355970177 252370435 261785751 379483303 572633804 337688626 372401826 547269677 96130846 73438099 661421955 698181379 572090230 450479934 228641241 147805811 738826594 141119123 56805046 238788468 28829394 458675039 417236833 546233163 398612491 89458260 222016546 6165230 50549244 660467933 595941819 406519421 275427495 220316696 148591851 210650425 558005322 520993677 2883715 654136168 712057290 26894796 597281160 646736646 100 100 0 0 1000000 9150 9150 14027 14027 45909 45909 84040 84040 85672 85672 108520 108520 120135 120135 145736 145736 154356 154356 157762 157762 180205 180205 190810 190810 196517 196517 197344 197344 221332 221332 225200 225200 281919 281919 283461 283461 285830 285830 291387 291387 316560 316560 337457 337457 338674 338674 347293 347293 352665 352665 378037 378037 392064 392064 412003 412003 446888 446888 449258 449258 459659 459659 460718 460718 466464 466464 531827 531827 561284 561284 583243 583243 585334 585334 630144 630144 660039 660039 680073 680073 754748 754748 769112 769112 782678 782678 786603 786603 798659 798659 815682 815682 886575 886575 925403 925403 931139 931139 987944 987944
Problem Description Link: 
https://code.google.com/codejam/contest/32015/dashboard#s=p2
Problem Analysis Link: 
https://code.google.com/codejam/contest/32015/dashboard#s=a&a=2
Problem Id: 
23