**13 人解决**，38 人已尝试。

**14 份提交通过**，共有 93 份提交。

**7.2** EMB 奖励。

**单点时限: **2.0 sec

**内存限制: **256 MB

Operating system is the University required courses. Partychen decided to design a new program, a special program that is an Operating System! This is a multitask OS, processes can run at the same time on it, but when a procedures run,only a process has been created. And, processes cannot be created endlessly, they have a limit.Each procedure will take some time to run.So when there are many procedures have to run,you need to divide them in groups,let all the task end earlier.

For example,there are 9 procedure have to run,and they take 5,3,8,2,1,6,9,7,4 seconds separately.The OS only can run 3 processes.So you divided the procedure in 3 group,we divided them like 5,3,8|2,1,6|9,7,4,they takes16,9,20 seconds,so after 20 seconds,we can complete all procedure,but if we divided them like 5,3,8 | 2,1,6,9 | 7,4,they takes 16,18,11 seconds,so after 18 seconds,we can complete all procedure.

So give you a sequence of time of the procedure takes,you calculate the earliest time to complete all procedures.

The first line of input gives the number of cases, N(1 ≤ N ≤ 100). N test cases follow.

In each test case,the first line contains two interger m,n(1<=m,n<=100),m is the number of procedure,n is the number of processes the OS can run.Then m intergers follow.

For each test case, output a interger that is the earliest time.

Input

2 9 3 500 300 800 200 100 600 900 700 400 3 4 1000 1000 1000

Output

1800 1000

**13 人解决**，38 人已尝试。

**14 份提交通过**，共有 93 份提交。

**7.2** EMB 奖励。

题目标签