A team of M judges have been called to judge an episode of Masterchef India. There are N participants and the task given to them was to make an ice cream. The ice creams are judged based on the number of nuts they contain (the participants are unaware of this criterion). You are given the fact that participant i has put P[i] nuts in his ice cream. To make the judgement process fast, we are asked to divide these N ice creams within these judges so as to minimize the time taken to complete the process. Judges can take ice creams for judging only in order. i.e. If judge 1 takes the first M1 ice creams then Judge 2 can take only ice creams following M1, and so on. i.e. this ice cream sharing is a linear partition. (Order matters.) Each judge takes a unit time to count a nut. The time taken for completion is the time from the beginning of counting process to the time that the last judge finishes his job. Obviously that last judge will be the guy who was assigned maximum work (in terms of total number of nuts given to him.)

Thus, given the number of nuts contained in each ice cream, and the number of judges available, compute the minimum time, in which the judgement process can be completed.

Input

1st line contains T, denoting the number of test cases. Each test case is described in two lines as follows:

1st line contains N and M.

2nd line contains N integers denoting P[i] 1 <= i <= N

T <= 10

N <= 250

M <= N

P[i] <= 1000 for all I in [1, N]

Output

For each test case, output one integer containing the minimum of (maximum amount of time taken to complete the process.)

Example

Input:
1
5 4
1 2 3 4 5

Output:
5

Here the linear partition is: 1 2 / 3 / 4 / 5 (maximum work = 5)