Allocate Books

You are given an array of integers where each integer represents the number of pages in a book. There are N books arranged in order and you need to allocate them to K students. Each student must be assigned contiguous books. The task is to minimize the maximum number of pages assigned to any student.

Formally, if the books have pages A[1], A[2], ..., A[N] and they are split among K students, then let S_i be the sum of pages given to the i-th student. We want to minimize:

\( \min \{ \max_{1 \leq i \leq K} S_i \} \)

Use binary search on the potential answer to decide if a given maximum pages limit can be achieved with the available K students.

inputFormat

The input begins with an integer T, the number of test cases. For each test case, the first line contains two integers N and K, where N is the number of books and K is the number of students. The second line of each test case contains N space-separated integers representing the number of pages in each book.

outputFormat

For each test case, output a single integer on a new line representing the minimized maximum number of pages allocated to a student.

## sample

1
4 2
12 34 67 90

113

</p>