  # Untitled unknown
plain_text
a month ago
2.6 kB
0
Indexable
Never
```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 = 2
A = 1
A = 5
A = 1
A = 2
A = 2
A = 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;
, [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 = 2
A = 1
A = 5
A = 1
A = 2
A = 2
A = 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

#3 0
100
0
55
10
10
57
165

---------------------------------------------------------------------
10
3
7
2 1 5 1 2 2 2
4
10
10 2 1 5 1 2 2 2 9 11
10
10
0 0 0 0 0 0 0 0 0 0
1
10
10 10 10 10 10 10 10 10 10 10
1
1
0
1
10
1 2 3 4 5 6 7 8 9 10
10
10
10 9 8 7 6 5 4 3 2 1
9
10
1 2 3 4 5 6 7 8 9 10
3
10
20 19 18 17 16 15 14 13 12 11
14
100
1 2 3 4 5 6 7 8 9 0 11 22 33 44 55 66 77 88 99 12 12 13 14 15 16 17 18 19 10 0 9 12 12 34 23 25 27 28 29 10 10 1 2 3 4 5 6 7 8 9 0 99 12 12 13 14 15 16 17 18 19 77 88 99 12 12 13 14 15 16 17 29 10 10 1 2 3 4 5 6 7 12 13 14 15 16 17 18 19 20 23 24 25 26 2 3 41 8 0 10```  