Book Allocation Problem

Given (n) books with a specific number of pages, you are tasked with assigning these books to (k) employees such that each employee receives a contiguous block of books. The objective is to minimize the maximum number of pages allocated to any single employee. If it is not possible to assign at least one book to each employee (i.e. when (n < k)), the answer should be (-1).

Formally, given an array (P = [p_1, p_2, \dots, p_n]) representing the page counts of the books, partition (P) into (k) contiguous segments such that the maximum sum among these segments is minimized. This problem can be approached efficiently using binary search combined with a greedy strategy.

inputFormat

The input is provided via standard input. The first line contains two integers (n) and (k) separated by a space, where (n) is the number of books and (k) is the number of employees. The second line contains (n) space-separated integers representing the page counts of the books.

outputFormat

Output a single integer which represents the minimized maximum number of pages assigned to an employee. If a valid allocation is not possible (i.e. when (n < k)), output (-1).## sample

4 2
12 34 67 90

113