Problem Description

You are given an array of N positive integers. The array is partitioned into K subarrays. For any subarray, we define f(subarray i) as the sum of all the elements present in the subarray i.
M is the maximum of all f(subarray i), for i=1,2,3...,K
An optimal partition of the array is the partition which gives the minimum value of M. Your task is to find value of M for an optimal partition.
Note: A subarray consists of only adjacent elements of the array.

Input Specification

The first line of input contains T, the number of test cases.
Each test case consists of two lines.
The first line contains two integers N and K seperated by a space.
The second line contains N positive integers seperated by spaces.

Output Specification

For each test case, print M followed by a new line.

Constraints
• 1 <= T <= 500
• 1 <= N <= 1000
• 1 <= K <= N
• 1 <= elements in the array <= 106

Sample Input

4
3 2
15 20 10
5 3
19 1 10 11 20
4 1
9 9 9 9
8 4
8 7 1 1 1 2 9 2

Sample Output

30
21
36
11

Explanation

Case #1:
We can partition the array in two ways:
a) {15, 20} and {10}
b) {15} and {20, 10}
For parition(a), M = max(15 + 20, 10) = 35
For parition(b), M = max(15, 20 + 10) = 30
So partition(b) is the optimal partition and M = 30

Case #2:
Optimal parition is {19, 1} {10, 11} {20}
M = 10+11 = 21

Case #3:
Optimal parition is {9, 9, 9, 9}
M = 9 + 9 + 9 + 9 = 36

Case #4:
Optimal parition is {8} {7} {1, 1, 1, 2} {9, 2}
M = 9 + 2 = 11

Problem Setter: Rohan Laishram

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0