Minimize Maximum Segment Sum in Book Division

You are given a list of n positive integers representing the number of pages in each chapter of a book, and an integer k. The task is to divide the book into exactly k contiguous segments such that the maximum total number of pages in any segment is minimized. If k is greater than n, treat the division as splitting the book into n segments (each chapter being its own segment).

Formally, suppose the pages are represented as an array A of length n. You need to partition the array into segments such that if the sum of pages in each segment is S_i, then you minimize:

Print the minimum possible value of the maximum segment sum.

inputFormat

The input is read from stdin and has the following format:

n k
p1 p2 ... pn

Here, n is the number of chapters, k is the number of segments, and p_i represents the number of pages in the i-th chapter.

outputFormat

Output a single integer to stdout which is the minimized maximum segment sum after partitioning.

4 2
12 34 67 90

113