P20994 [HackerEarth] As we know students loves candies, so one day Teacher decided to give candies to M students. She brought along N boxes of candies. Box may contain any number of candies ranging from 1 to
普及
题目描述

As we know students loves candies, so one day Teacher decided to give candies to M students. She brought along N boxes of candies. Box may contain any number of candies ranging from 1 to 10^9. Teacher asked students to come one by one an take as many number of boxes they want , but boxes should be contagious ( in one row and without skipping any intermediate box) and always selection should begin from the first remaining boxes. Students get all the candies of the boxes he takes. After distribution of chocolates, teacher was in dilemma that a student may get very less chocolates comparatively to other students. So what is the maximum number of candies a students can have with minimum candies among all.
In short, you need to tell the maximum number of candies a student can get , by making a distribution in which this student has minimum number of candies among all others.

INPUT
T – number of test cases
Each T line containing, N and M where N is number of boxes and M is number of students.
N integers containing number of candies in each box.
OUTPUT
T lines containing a single integer denoting number of maximum candies a student can get which has minimum candies among all other students.

Constraints
1 ≤ M ≤ 10^5
1 ≤ N ≤ 10^5
Number of candies in a box 1 ≤ Number ≤ 10^9
N ≥ M

SAMPLE INPUT
2
3 2
1 3 2
3 1
4 4 4

SAMPLE OUTPUT
2
12

输入格式

见题面

输出格式

见题面

样例输入
10 100 10 64117237 332893598 42811967 5813933 8494207 6524593 160416452 6069467 41673091 64310149 30755541 9126320 2124741 3789620 8663193 9892604 695602 8146596 9593724 7366587 5920631 9333984 7678874 6603620 9219609 51222219 6046822 4104311 3695359 4726887 890819 4777708 530251 8055474 5746378 4341912 8463547 3765234 57864591 3261282 80542015 23606002 515379 6181349 5047326 5876863 9861339 35391887 623801881 2784379 5883387 22093526 93301614 4056492 7050031 6740115 569046912 93009586 4236613 8419352 95291455 6554277 622604917 9305979 2938308 6719266 2113063 574658 1706494 4916369 4681986 4770408 3649711 2142663 2371082 75445159 3539516 8175441 41864300 6471612 7165092 4347766 90278636 1841552 13321082 6138059 5687919 19334583 470141110 5070071 4386935 3837730 6279743 1037058 3334160 6882618 8101124 9053678 4227733 6260297 100 10 43869685 14899024 409111279 2846309 3176771 2430822 1696794 7095438 4105050 1360253 7157651 4318373 1141959 9316633 9709600 9104222 4134045 8710023 3134621 1761619 5917051 126886455 1636609 5628895 7268464 6865867 1167197 5871021 8884466 41911273 326763033 13625198 65656195 8837190 1474045 5197345 1121170 6554277 832760 3029279 8089462 1502632 612842 87136389 501549579 6614750 1916132 660258011 8946567 4397483 793771856 6166286 6540160 4892200 5733950 997586604 8156000 40396090 6836048 2444785 4708904 6847472 3148559 1468392 7408153 4997847 39185774 3975760 7007535 4545580 6334573 7589175 4613426 71042656 511596 3557023 5365332 9961074 9581474 2047430 1851638 8937561 9406473 5415352 3882344 85208150 1720041 1051315 4147191 9109467 2337250 6581398 87463433 3917085 543758072 899491 3513546 9021474 3954553 1790734 100 10 308795742 7695821 1326544 9080832 924637 344341 2349510 6467026 3359540 2494728 1713238 1549074 81657632 3308915 7032009 8854849 2940425 2744302 3163712 7334547 1264680 3926853 1736052 3736725 2468266 6691017 6612826 6824010 6414876 9587011 141771912 9129337 2176511 3599810 5015459 6595629 7328823 5518639 6684059 4677464 6955795 2686045 9379433 5952200 2843419 8683430 5854488 867224153 1046187 3788997 34358288 4491814 5718667 9987716 3061040 8531564 8787935 4106438 4332022 9354134 3489202 1041154 8527778 8095932 3292764 748096399 3350102 8249266 9950016 5773860 56997662 5307226 6364608 773063 8324549 856579122 4947553 5517910 26727543 9176344 47700745 902877 3733218 6730165 6442898 5979050 435218899 646916 7892805 3695302 8408443 3654711 969417 478041682 8504727 4044462 6537300 2589831 710084562 5602971 100 10 652338 3320588 5740621 713847 4912041 4720880 8732208 2249313 7103846 6375800 334279562 7987344 6518916 7946768 470782785 7755941 1110049 1524217 643314258 9565034 8600724 539320466 6069938 7538794 126751094 895901 298628 2156162 6333605 5505196 2824831 826234 1512447 7105921 5133007 5241101 7352893 9046640 166152 5940300 8565311 69169403 8150218 2555738 185872 80037828 85633026 9960077 8153443 713433693 3055928 3850068 1477406 1214760 632644132 7472993 2669965 3787189 3964060 1358235 898425069 9003711 2907605 8072041 8919074 797952646 483499253 45319278 7998638 1273684 6636993 372276 4360164 8654292 8476249 3386584 58403518 23756144 294950955 7983524 1755197 3948410 4359493 7094850 3790502 4518962 7933288 5657807 80489146 4934929 718355567 59379795 7482285 6156554 8435562 3248364 2694161 7643402 7380443 71545328 100 10 4252002 7221615 7984007 4581485 1395254 5032479 1641050 7684315 960584 4221088 4009544 2208697 6900388 8438052 4389929 950244 872071398 8458902 676595 8851433 6232167 1868105 36074680 8220199 1501988 4362413 4402881 3598767 1800872 2625928 5623594 492301171 4943509 9140926 1905378 5163101 6501329 2832137 9818452 5250404 4233065 7881336 507805470 2281607 7485317 72920821 1865628 6264027 59104158 8688025 4672649 4068212 217219605 200039 5050880 3178743 7863586 517299 1006491 5561096 2122653 3028603 139627275 95792850 6104661 3457252 355970883 4772555 950506 7965644 1947733 918496321 7638294 2579380 8901962 5146454 5038705 8553062 348683000 7636187 6149732 5237566 3766001 9195420 763386665 5010366 5344440 8149957 3014772 4401655 4556809 4103822 4631021 4385541 349269388 1136390 5253907 523412399 9459639 9822737 100 10 5840274 7688440 9992861 9721587 238619363 24716083 729552841 620683416 2694980 1723111 7947809 2028136 1945929 2342602 6980951 87678737 93030177 9025737 201064486 365794 2401356 5509335 4625926 8817938 85636437 352478816 4773631 75052430 1948410 6041287 3620753 196838134 1640172 482659 343059 8547508 4305977 8993371 310262745 4475534 8819534 1839872 6140254 8008971 1945893 6909024 4204050 12602053 403149697 9805947 5948251 5124598 8122708 69289149 71508074 6989537 4338941 5900594 3722420 2457746 8509506 5882155 2010769 1843937 7082773 1487913 531810776 7863212 694327721 8906817 7358712 8040641 3284154 3046248 6290028 241983 949609639 1758973 1863532 279082544 7175696 4550994 153384041 704103 8438082 5886669 9960959 3036078 40209281 2895633 937832699 7854354 6858833 851707 331179209 7339977 88220591 1917222 1414704 3150269 100 10 7820842 8063087 543517719 6515013 8086136 57800716 8357108 856483815 57402191 3082697 71592428 8532911 454376612 7870926 6990968 43925305 5869851 9965687 47733529 9594053 39903839 3917372 145648080 9373009 90794306 4184328 250981 264626550 4414736 6238070 9642607 9478975 3155640 352107 58653290 8773267 1570289 602759241 4453141 4068955 2428556 905006 6330731 9246473 2221281 319581514 5858596 7847256 1885164 339634095 6957930 19804712 7347428 1170355 426685315 4027346 6049451 7696089 7584260 51762128 7222354 90953188 3553947 5009235 5052475 9124658 8583575 72903223 342660 6857697 749135005 92612535 8404371 4568637 36782367 5659811 2278072 75672787 3518322 934795804 2168977 6834182 5520174 3883764 2126039 4303895 1755885 118211 274764675 84206643 8236354 4683242 2817040 1347784 2692900 4617754 6643286 5571580 756132 807556611 100 10 3583108 95717421 2257835 4405222 818084931 9652398 7827736 9199242 2030148 1738353 9854184 77196900 5948991 9354735 6289636 2030445 6871328 142064928 9332408 9651243 670366 3148749 8835287 2734680 8495462 5016734 53542273 1937550 3039973 2394349 8708755 3011589 43219428 829143 2147392 7752014 8286592 3606022 2306153 9073193 4244778 1705346 575049 8427294 70002402 7584782 824335 5197483 9288999 2768187 6039825 3205122 7986486 735841 141753 8172573 4782712 2339343 9814214 9020129 3204484 6757023 6512658 1550120 6338680 8593499 8701516 4376896 7409954 803031390 56177707 9310785 10625713 3227379 4576692 1457958 5401883 1475951 356128502 2242331 47863789 1162478 6569041 9552739 8106096 18507672 433911658 5972635 933806 9325199 1762087 5482610 45148607 202786704 4082413 5316987 608099 7142742 6698671 8289572 100 10 8700125 1031628 1154644 6195693 8106051 210577 8947136 8516872 7018803 4271349 523022 223413 4004475 6300786 8023515 8820775 6532166 201117 5814207 49149517 719774 4040028 3358227 3691992 5510919 3348587 288537 6145526 5390419 3051891 7338192 8991054 5076199 42787913 2290891 92181450 74182771 734537343 1153270 9253329 9328429 3901804 6459887 1212382 149774809 9661410 189869093 7868939 570724845 7395685 6090764 7841510 9955551 3093009 4901440 8960895 2361066 2791496 21080937 70825202 6513118 2257041 4747321 23993498 6303574 5688791 883552 27897085 87657884 6411081 4584904 8311796 589990 6357752 1695548 9388415 65924675 2669817 8852687 548915999 7488713 3488346 217033 4074624 5696500 4722583 790494505 5404876 417486393 4661089 608530 8865992 1161068 3381669 5404607 985408994 3538950 591558 8967740 3173743 100 10 4569396 4434719 4916310 6825949 3490399 4774714 7399817 69549690 2579845 155002 6403406 3022028 5684350 4264290 6552426 935265505 4892098 8760147 3149539 8513024 7148968 8978094 38617561 9199988 89710213 4075311 5166772 8625407 1147371 3365126 1644543 4742559 9030811 2536527 1643898 989145573 4921034 64529953 5842695 4607391 969697738 9093034 9947878 627688473 7323690 1313000 263010993 2941471 382954 8946007 3066817 9938648 559675 5088693 6377842 4615227 3191682 2277493 390614461 3883763 2928099 835518258 8661625 458011541 2073556 52174971 815458908 197067 834439375 6877825 5862062 225050 2316285 1291881 9085713 9345355 4969916 2143506 8106684 515447 5876096 174225 74110298 469222508 8309868 4481597 9598649 6966605 191384 2480265 7816677 504569 7391332 7203740 5867164 5813144 1714963 6784817 5182841 5914918
样例输出
207511283 242657602 122011632 538090853 399258068 518946585 640160621 123761832 202444549 520921693