PROBLEM CODE:Enigma Treasure Hunt

KaushikRamDonn went to Enigma and registered for 

Treasure Hunt.Following are the rules for Enigma Treasure hunt ,

Rule 1: Donn has to go from 1st stage to nth stage in a sequential order ( only after completing stage 1 ,he can go to stage 2,then to stage 3). 

and collect treasures in a bag

Rule2: Donn will be given only k bags at the time of registration

Rule3: There are bags capable of holding all possible weights and is infinite in number. Donn is free to choose any bags capable of holding any weight (but all the k bags should be capable of holding the same weight)

Pandian,the organiser will give the bag to Donn.

Rule4: once the game is started ,Donn cant exchange his bag .

Rule5: While going through different stages,if Donn couldnt accomodate the treasure in a bag ,he will tie the bag and give it to Pandian.(this bag cant be used any more).Then he starts collecting the treasures in a new bag.

Rule6: The cost of the bag is directly proportional to the weight it can hold ,so try to reduce the cost.

Fortunatley ,Donn knows the weights of the treasure in each stage ,Help Donn Choose his bag.

Example: 

Consider there are 3 stages(n= 3) in the Hunt.the weight of the treasures in each of these stages (which is known to donn before the hunt starts)

are 1,2 and 3. Donn is  allowed to get 2 bags(k= 2) in this example

n = 3, k= 2

stages = {1,2,3}

Donn could accomplish his target if each of his bag can accomodate 3 kg or 5 kg.

Explanation :

if the wieght of the bag is 3 - Stage1 weight + stage2 weight = 1+2=3 <=3 in one bag ,stage 3 weight= 3<=3  in another bag.thus they fit in the bags

if the wieght of the bag is 5 - Stage1 weight = 1<=5 in one bag,stage2 + stage 3 weight= 2+3 =5 <=5 in another bag.thus they fit in the bags

but consider a bag size of 2 :

1 + 2> 2 so put stage1 treasure alone in 1st bag

2 + 3 >2 so put stage2 treasure alone in 2st bag

now we need one more bag to put in the 3rd treasure.

This is not possible so u cant choose a bag of size 2

bag of size >=3 can be used 

Donn is intelligent and so he wants to pay the minimum cost so Donn will purchase a bag of size 3.Help Donn solve his problem .

Input:

0< T <=100 ,no of test cases 

Each test case contains

0<N<=1000,no of stages and then a space followed by

0<k<=1000, no of bags allowed

the next N lines contains the weights of the treasures in each stage
the weight of the treasure <= 1000 . 

output:

output a single line containing the minimum size of the bag needed.

Example

Input:

1

3 2

1

2

3

output :

3