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 <= A

1< n < 100

1< m <= 50

1 <= A

_{i}<= 1000Loading...

View Submissions

Console