## SEQPAR - Partition the sequence

no tags

Given an integer sequence containing n elements (numbered from 1 to n), your task is to find the minimum value M so that we can find k + 1 integers 0 = p(0) < p(1) < p(2) < ... < p(k-1) < p(k) = n, such that for any i from 0 to k - 1, the sum of elements from postition p(i)+1 to postition p(i+1) is not greater than M.

### Input

The first line of input contains the number of test cases nTest (1 <= nTest <= 10).

Each test case contains:

The first line contains n, k. (1 <= k <= n <= 15000)

Each of the next n lines contains an integer of the sequence with value range from -30000 to 30000.

### Output

For each test case write the minimum number M in a separate line.

### Example

```Input:
1
9 4
1
1
1
3
2
2
1
3
1

Output:
5
```

hide comments Prismatic: 2015-07-15 07:51:10 I used BS + BIT + compress data :D AC in QBSEQPAR humble_coder: 2015-01-23 19:54:47 the question basically is to find the minimum value of M such that we can partition the array into k subarrays such that - each subarray's sum <= M Dominik Kempa: 2009-08-18 21:29:07 5 is minimal number such that sequence can be partitioned into 4 parts such that sum of each is not greater than 5, this partition is (for example): [1,1,1], [3,2], [2,1], [3,1] Last edit: 2009-12-03 08:19:25 Frane Kurtoviæ: 2009-07-23 12:58:03 Can anyone explain provided test case? I am not sure that I understood the task correctly.

 Added by: Nguyen Dinh Tu Date: 2006-01-02 Time limit: 7.414s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS PERL6 VB.NET Resource: Viet Nam Olympiad in Informatic 2005, Day I