Book Allocation Problem

You are given a list of n books where each book has a certain number of pages. The task is to allocate these books to k students in a contiguous manner in order to minimize the maximum number of pages assigned to any student.

If k is greater than the number of books, the allocation is considered invalid, and the program should output -1.

The problem can be solved using a binary search approach. You need to determine the minimum possible value of the maximum pages any student gets while allocating books contiguously.

For example, if there are books with pages [12, 34, 67, 90] and k is 2, one optimal allocation is [12, 34, 67] and [90] with the maximum pages being 113 (i.e. 12+34+67). Hence, the answer is 113.

Formula: If we denote the allocation as partitioning the array into k contiguous segments, then our goal is to minimize:

$$\min \max_{1\le i \le k} \{\text{sum of pages in segment } i\} $$

inputFormat

The input is read from stdin and consists of three lines:

• The first line contains an integer n which is the number of books.
• The second line contains n space-separated integers representing the number of pages in each book.
• The third line contains an integer k which is the number of students.

If k is greater than n, the program should output -1.

outputFormat

The output should be printed to stdout, and it is a single integer representing the minimum possible maximum number of pages assigned to any student given the allocation constraints.

## sample

4
12 34 67 90
2

113