You are given an array of n non-negative integers and an integer k. Partition the array into exactly k non-empty contiguous groups (every element belongs to exactly one group, groups keep the original order). Among all such partitions, choose the one that minimizes the largest group sum. Return that minimized largest sum.

The answer is a single well-defined value. The intended approach binary-searches on the candidate largest sum: for a candidate limit L, a greedy left-to-right sweep counts the minimum number of groups whose sums each stay within L; feasibility is monotonic in L.

Input format

Line 1: an integer n, the length of the array. Line 2: n space-separated non-negative integers. Line 3: an integer k, the number of contiguous groups (1 ≤ k ≤ n).

Output format

A single integer: the minimum possible value of the largest group sum.

Constraints

• 1 ≤ n ≤ 100000
• 0 ≤ each array value ≤ 1000000
• 1 ≤ k ≤ n

5
7 2 5 10 8
2

18

4
1 2 3 4
3

4