Distribute Books

You are given a collection of books and the number of pages in each book. The books must be allocated to M students, with each student receiving at least one book. The books are arranged in the given order and must be distributed consecutively. Your task is to minimize the maximum number of pages that any student has to read. If it is impossible to allocate (i.e. when the number of books is less than the number of students), output -1.

The problem can be modeled by determining the minimum possible value (X) such that the books can be partitioned into M contiguous segments, with the sum of pages in each segment not exceeding (X). A binary search approach can be used to find (X) efficiently.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer (T) representing the number of test cases.
• For each test case, the first line contains two integers (N) and (M), where (N) is the number of books and (M) is the number of students.
• The next line contains (N) space-separated integers, each representing the number of pages in a book.

Constraints: (1 \leq N, M \leq 10^5). Books must be allocated in the order in which they appear in the input. If (N < M), output -1 for that test case.

outputFormat

For each test case, output one line containing a single integer which is the minimized maximum number of pages that a student needs to read. If it is impossible to allocate the books as required, output -1.## sample

1
4 2
12 34 67 90

113