You are given an array of KaTeX can only parse string typed expression integers where each element KaTeX can only parse string typed expression represents the number of pages in the KaTeX can only parse string typed expression-th book. You are also given an integer KaTeX can only parse string typed expression representing the number of students.
Your task is to allocate the books to the students such that:
-
Each student receives at least one book.
-
Each student is assigned a contiguous sequence of books.
-
No book is assigned to more than one student.
The goal is to minimize the maximum number of pages assigned to any student. Among all valid allocations, find the arrangement where the student who receives the most pages still gets the minimum possible maximum pages.
If it is not possible to allocate books so that every student receives at least one book, print KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers representing the pages in each book — KaTeX can only parse string typed expression.
4 2
12 34 67 90
Output
113
Explanation
Possible allocations:
(1) [12] and [34, 67, 90] → Maximum pages = 191
(2) [12, 34] and [67, 90] → Maximum pages = 157
(3) [12, 34, 67] and [90] → Maximum pages = 113
The third allocation gives the minimum possible maximum pages, which is 113.
Input
3 5
15 17 20
Output
-1
Explanation
There are more students than books, so it is impossible to give at least one book to every student.