Split Array Largest Sum

You are given an array of positive integers and an integer k. Your task is to partition the array into k contiguous subarrays (each subarray is non‐empty) such that the largest sum among these subarrays is minimized. More formally, if the array is denoted as \(a_1, a_2, \dots, a_n\), you want to split it into k parts so that the value
\[ \min \max_{1 \leq i \leq k} S_i \quad \text{where} \quad S_i = \sum_{j \in A_i} a_j \]
is as small as possible. A standard approach is to use binary search on the answer within the interval \([\max\{a_i\}, \sum_{i=1}^{n} a_i]\) combined with a greedy algorithm to check if a given maximum sum is feasible.

inputFormat

The input begins with a single integer indicating the number of test cases. For each test case, the first line contains two integers n (the number of elements in the array) and k (the number of subarrays to partition into). The next line contains n space‑separated positive integers representing the array elements.

outputFormat

For each test case, output the minimum possible value of the maximum subarray sum after partitioning. Each answer should be printed on a new line.

3
5 2
1 2 3 4 5
4 2
10 20 30 40
6 3
1 1 1 1 1 10

9
60
10