Notebook Allocation

You are given n notebooks and an array pages where each element represents the number of pages in a notebook. The notebooks are arranged in a fixed order. Your task is to assign these notebooks to k students such that each student receives a contiguous segment of notebooks and every student gets at least one notebook. The goal is to minimize the maximum number of pages assigned to any student.

Formal Description:

Let \(pages = [p_1, p_2, \dots, p_n]\) be an array of positive integers and \(k\) be a positive integer. Partition the array into \(k\) contiguous segments such that if \(S_i\) is the sum of pages in segment \(i\), then you want to minimize \(\max(S_1, S_2, \dots, S_k)\). Output this minimized maximum value.

Example:

• For \(n = 4\), \(pages = [12, 34, 67, 90]\) and \(k = 2\), one optimal partition is \([12, 34, 67]\) and \([90]\) which gives sums \(113\) and \(90\), so the answer is 113.

inputFormat

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

1. An integer (n), the number of notebooks.
2. A line with (n) space-separated positive integers representing the number of pages in each notebook.
3. An integer (k), the number of students.

Example input: 4 12 34 67 90 2

outputFormat

Output to stdout a single integer which is the minimized maximum number of pages assigned to any student.## sample

4
12 34 67 90
2

113