#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/f

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/f

Repovive

Circular Delivery - Repovive Career Starter Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

7F. Circular Delivery

3000 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

You are given a circle with $n$ points. At point $i$ , there are $a_i$ packages.

You have to choose exactly $k$ different gaps between adjacent points and cut the circle there. These cuts divide the circle into exactly $k$ non-empty contiguous parts.

The cost of a part is the sum of the packages inside it. Your task is to minimize the maximum cost among the $k$ parts.

For example, because the array is circular, one part may contain $a_{n-1}, a_n, a_1$ .

You have to solve the problem for $t$ test cases.

Constraints

$1 \le t \le 10^4$
$1 \le k \le n$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

5 2
3 1 2 8 2

Case 2

4 4
5 1 7 3

Case 3

6 3
4 2 6 1 3 5

Case 4

7 3
10 1 1 1 10 1 1

Case 5

8 3
2 9 2 2 9 2 2 2

Explanation

Case 1

The circle can be split into parts with sums $8$ and $8$ , for example $[8]$ and $[2,3,1,2]$ . Therefore the maximum cost can be $8$ .

Case 2

Every part must contain exactly one value because $k=n$ . The largest value is $7$ , so the answer is $7$ .

Case 3

One optimal split has sums $6$ , $7$ , and $8$ , for example $[4,2]$ , $[6,1]$ , and $[3,5]$ . Hence the maximum cost is $8$ .

Case 4

A split with maximum cost $11$ is possible: $[1,1,1]$ , $[10,1]$ , and $[1,10]$ . The last part uses the circular order.

Case 5

A split with maximum cost $11$ is possible: $[9,2]$ , $[2,9]$ , and $[2,2,2,2]$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given a circle with $n$ points. At point $i$ , there are $a_i$ packages.

You have to choose exactly $k$ different gaps between adjacent points and cut the circle there. These cuts divide the circle into exactly $k$ non-empty contiguous parts.

The cost of a part is the sum of the packages inside it. Your task is to minimize the maximum cost among the $k$ parts.

For example, because the array is circular, one part may contain $a_{n-1}, a_n, a_1$ .

You have to solve the problem for $t$ test cases.

$1 \le t \le 10^4$
$1 \le k \le n$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

The circle can be split into parts with sums $8$ and $8$ , for example $[8]$ and $[2,3,1,2]$ . Therefore the maximum cost can be $8$ .

Every part must contain exactly one value because $k=n$ . The largest value is $7$ , so the answer is $7$ .

One optimal split has sums $6$ , $7$ , and $8$ , for example $[4,2]$ , $[6,1]$ , and $[3,5]$ . Hence the maximum cost is $8$ .

A split with maximum cost $11$ is possible: $[1,1,1]$ , $[10,1]$ , and $[1,10]$ . The last part uses the circular order.

A split with maximum cost $11$ is possible: $[9,2]$ , $[2,9]$ , and $[2,2,2,2]$ .