Sameer is a huge patriot. He can do anything for his country. After graduation, he leaves all his lucrative job offers, and joins the super-secret organisation, Indian National Digital Intelligence Agency, where many like-minded geniuses work hard to intercept and decipher any secret encoded messages exchanged by enemy countries, terrorists, and the like, for the security of the country.

One day, a major breakthrough is reached, when a critical message is intercepted by the organisation. The message is really huge, and is stored on N disks (numbered 0 to N-1 serially). The amount of data stored on each disk is different. To decode the message, M of the best employees (including Sameer of course) are chosen. To avoid repetition and confusion, it is decided that 1 disk will have to be completely decoded by exactly 1 person. Also, one person can decode any number of disks, provided that all of them are contiguous in serial order (i.e. one person cannot decode disc numbers 1, 4 or 2, 3, 5 etc.)

All the employees work in parallel and have identical decoding speeds of 1 byte per second. Now, the head of the organisation wants to assign the disks in such a way that the total time taken to decode all of them is minimised. He assigns the task of finding this minimum time to Sameer. Can you help Sameer out?

Note: It is possible that some of the M employees do not decode even a single disk.

Input

First line contains T, the number of test cases.

The first line of each test case contains 2 space separated integers, N and M (as described above).

The next line contains N space separated integers, denoting the number of bytes of data on each of the discs.

Output

For each test case, output a single integer showing the minimum time (in seconds) to complete decoding.

Contraints

1 <= T <= 10

1 <= N <= 3000

1 <= M <= N

0 <= Number of bytes on each disk <= 1000000000

Example

Input:
2
3 2
1 2 3
5 3
1 2 3 4 5

Output:
3
6

Explanation

In the first test case, the first employee can decode the first 2 disks and the second employee can decode the third disk.