Problem Statement

Little Atom has $N$ toys, which she has arranged in a sequence. The $i$-th toy has a value of $A_i$, and she wants to place these toys into $M$ boxes in order. You can decide how to partition these toys into boxes, but the toys in each box must have consecutive indices. The value of each box is defined as the sum of the values of all toys inside it.

Little Atom wants to know the maximum possible value of the smallest box value among all possible ways to partition the toys.

In other words, after partitioning the toys into $M$ boxes, the smallest box value should be as large as possible. Please help her determine this value.

Input Format

The first line contains two positive integers $N$ and $M$, representing the number of toys and the number of boxes, respectively.

The second line contains $N$ non-negative integers $A_1, A_2, \dots, A_N$, representing the value of each toy.

Output Format

Output a single integer, representing the maximum value of the smallest box among all possible ways to partition the toys.

Sample #1

Sample Input #1

5 2
1 2 3 4 5

Sample Output #1

6

Explanation

• One possible way to partition the toys into two boxes is [1, 2, 3] and [4, 5]. In this case, the value of the smallest box is 6, which is the largest possible value for the smallest box.
• If partitioned as [1, 2] and [3, 4, 5], the smallest box value is 3.
• The optimal solution is to partition the toys so that the smallest box value is 6.

Constraints

$1 \leq N \leq 10^5$, $M \leq N$. $0 \leq A_i \leq 10^8$.