Minimal Cleaning Time Allocation

You are given a sequence of tasks where each task denotes the cleaning time of a room. There are N rooms and K cleaning staff available. The rooms must be assigned to the cleaning staff in order (i.e. contiguous segments) such that each staff member is allocated a contiguous block of rooms. The goal is to find the minimal possible maximum cleaning time among all staff members. In other words, you need to minimize the time taken by the slowest staff member.

More formally, given room cleaning times a₁, a₂, ... , a_N, partition the sequence into K segments. Let S_i be the sum of cleaning times in segment i. You need to minimize max(S₁, S₂, ..., S_K). It is guaranteed that a valid allocation exists if each task is done by some staff.

The answer can be obtained by using binary search to decide the minimum possible "maximum cleaning time" that is sufficient to allocate tasks among K staff.

Hint: Use a binary search on the answer space [max(rooms), sum(rooms)] and check for each candidate time if a valid allocation is possible.

inputFormat

The first line of input contains a single integer T (1 ≤ T ≤ 100) representing the number of test cases.

For each test case:

• The first line contains two integers N and K (1 ≤ K ≤ N ≤ 10⁵), where N is the number of rooms and K is the number of cleaning staff.
• The second line contains N integers, each denoting the cleaning time required for each room. Each cleaning time is a positive integer not exceeding 10⁹.

outputFormat

For each test case, output a single line containing the minimal possible maximum cleaning time required to assign the rooms such that no staff member exceeds that cleaning time.

## sample

1
5 3
10 20 30 40 50

60

</p>