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