Allocate Books

Books with pages[i] pages are in a row. Give each of students students a run of consecutive books, so that every book goes to exactly one student and every student gets at least one book. Among all ways to do this, return the smallest possible value of the largest page total given to any one student.

If there are fewer books than students, return -1.

Examples

Example 1

Input:

allocate_books([12, 34, 67, 90], 2)

Output:

113

Split 12 34 67 (113) and 90: the largest is 113.

Example 2

Input:

allocate_books([10, 20], 3)

Output:

-1

There are fewer books than students.

Constraints

• 1 <= len(pages) <= 2 * 10**4
• 1 <= students <= 2 * 10**4
• 1 <= pages[i] <= 10**4
• Trying every limit one by one is too slow for the large tests.