A chocolate bar is a row of n chunks, chunk i having sweetness s[i]. You will break the bar into exactly p contiguous, non-empty pieces (each piece is a run of neighboring chunks, and together the pieces cover the whole bar with no gaps or overlaps). The sweetness of a piece is the sum of its chunks.
After splitting, the weakest piece is the one with the smallest total sweetness. Choose the split that makes the weakest piece as sweet as possible, and report that weakest piece's sweetness.
Input format
Line 1: two integers n and p.
Line 2: n space-separated integers, the chunk sweetness values.
Output format
A single integer: the maximum possible sweetness of the weakest piece.
Constraints
- 1 <= p <= n <= 40
- 1 <= each sweetness <= 100000