Taco Book Stacking

You are given n books, where each book has a certain number of pages, and an integer k representing the number of stacks. Your task is to partition the books into exactly k contiguous stacks such that the maximum total number of pages in any stack is minimized.

In other words, if the books are divided into stacks with sums \(S_1, S_2, \dots, S_k\), you need to minimize \(\max(S_1, S_2, \dots, S_k)\). A binary search based strategy can be used to determine the smallest possible maximum sum. The key observation is that:

\[ \max(\text{pages}) \leq M \leq \sum_{i=1}^{n}\text{pages}[i] \]

Your algorithm should determine the minimal value of \(M\) such that the books can be partitioned into k stacks without any stack having a sum exceeding \(M\).

inputFormat

The input begins with an integer T denoting 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 stacks.
• The second line contains n space-separated integers representing the number of pages for each book.

outputFormat

For each test case, output a single integer on a new line: the minimal possible value of the maximum number of pages in any stack after partitioning the books optimally.

## sample

1
6 3
5 7 2 6 8 3

12

</p>