Divide Chocolates Problem Statement

Ninja bought chocolate consisting of several chunks, and the sweetness of each chunk is represented in an array ARR. He wants to divide the chocolate into K + 1 parts (cuts), where K is the number of his friends. Ninja desires to take only one part with the minimum total sweetness.

Your task is to maximize the total sweetness of the part that Ninja will get based on the condition stated above.

Input:

The first line contains an integer ‘T’, representing the number of test cases.
 For each test case, the first line consists of two space-separated integers, ‘N’ and ‘K’, indicating the number of chunks and the number of friends.
 The second line for each test case contains ‘N’ space-separated integers representing the sweetness of each chunk in ‘ARR’.

Output:

For each test case, provide the maximum sweetness that Ninja can obtain under the given condition.

Example:

Input:

2
6 2
6 3 2 8 7 5
7 3
1 6 2 3 1 2 8

Output:

15
9

Explanation:

In the first example, by making 2 cuts, Ninja can take a part with the maximum minimum sweetness of 15.
In the second example, making 3 cuts allows Ninja to take a part with the maximum minimum sweetness of 9.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 50000
• 0 ≤ K < N
• 1 ≤ ARR[i] ≤ 10000
• Time Limit: 1 sec

Note:

Implement the function to determine the maximum sweetness, printing is handled elsewhere.