802. Book Distribution Challenge

0

Hard

Given a set of n books with varying numbers of pages and m students, the books are arranged in ascending order based on the number of pages. Each student is assigned to read a consecutive set of books. The objective is to distribute the books in a way that minimizes the maximum number of pages assigned to any student.

Input Format

The first line contains an integer t, representing the number of test cases. The next t lines contain two lines each. For each test case, the first line contains two integers n and m, representing the number of books and students respectively. The second line contains n space-separated integers, representing the number of pages of the n books in ascending order.

Output Format

Print the maximum number of pages that can be assigned to the students.

Example

Input

1 4 2 12 34 67 90

Output

113

Constraints

1 < t < 50
1< n < 100
1< m <= 50
1 <= Ai <= 1000
Loading...

View Submissions

Console