Talented Chef

Time Limit: 2 Seconds
Memory Limit: 65536 KB

As we all know, *Coach Gao* is a talented chef, because he is able to cook `M` dishes in the same time. Tonight he is going to have a hearty dinner with his girlfriend at his home. Of course, *Coach Gao* is going to cook all dishes himself, in order to show off his genius cooking skill to his girlfriend.

To make full use of his genius in cooking, *Coach Gao* decides to prepare `N` dishes for the dinner. The `i`-th dish contains `A`_{i} steps. The steps of a dish should be finished sequentially. In each minute of the cooking, *Coach Gao* can choose at most `M` different dishes and finish one step for each dish chosen.

*Coach Gao* wants to know the least time he needs to prepare the dinner.

#### Input

There are multiple test cases. The first line of input contains an integer `T` indicating the number of test cases. For each test case:

The first line contains two integers `N` and `M` (1 <= `N`, `M` <= 40000). The second line contains `N` integers `A`_{i} (1 <= `A`_{i} <= 40000).

#### Output

For each test case, output the least time (in minute) to finish all dishes.

#### Sample Input

2
3 2
2 2 2
10 6
1 2 3 4 5 6 7 8 9 10

#### Sample Output

3
10

Submit
Status