# Optimal Partition

**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 <= 10
^{6}

**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