# Untitled

unknown
plain_text
2 months ago
1.9 kB
2
Indexable
Never
```Minimal Big Sum
Suppose 'A' is a non empty zero indexed array of 'N' integers and 'K' is another Integer.
Array 'A' needs to be divided into 'K' blocks of consecutive elements.

﻿
Size of the block is any integer such that , 0 <= size of block <= N. Every element of the array should belong to some block.

The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.

The big sum is defined as the maximal sum of any block.

﻿

For example, you are given integers 'K' = 3 and array A such that:
A[0] = 2
A[1] = 1
A[2] = 5
A[3] = 1
A[4] = 2
A[5] = 2
A[6] = 2

The array can be divided, for example, into the following blocks:

[2, 1, 5, 1, 2, 2, 2], [], [] with a big sum of 15;
[2], [1, 5, 1, 2], [2, 2] with a big sum of 9;
[2, 1, 5], [], [1, 2, 2, 2] with a big sum of 8;
[2, 1], [5, 1], [2, 2, 2] with a big sum of 6.

﻿

The goal is to minimize the big sum. In the above example, 6 is the minimal big sum.

﻿

Given integer K and a non-empty zero-indexed array A consisting of N integers, returns the minimal big sum.

﻿

For example, given K = 3 and array A such that:
A[0] = 2
A[1] = 1
A[2] = 5
A[3] = 1
A[4] = 2
A[5] = 2
A[6] = 2

the function should return 6, as explained above.

﻿

Assume that:

N and K are integers within the range [1..100,000];
each element of array A is an integer within the range [0..M].﻿

Input :
First Line : T : Number of test cases
Second Line : K : Number of Blocks.
Third Line : N : Number of elements in the input array
Fourth Line : Elements of array separated by space.
Fifth Line : next test case follows

﻿

Output
#Test_Case minimized_big_sum

﻿

Sample Input
2
3
7
2 1 5 1 2 2 2
4
10
10 2 1 5 1 2 2 2 9 11

﻿

Sample Output

#1 6
#2 12

```