You are given an array containing n positive integers.

Your task is to divide the array into k subarrays so that the maximum sum in a subarray is as small as possible.

Input

The first input line contains two integers n and k: the size of the array and the number of subarrays in the division.

The next line contains n integers x_1,x_2,\ldots,x_n: the contents of the array.

Output

Print one integer: the maximum sum in a subarray in the optimal division.

Constraints

• 1 \le n \le 2 \cdot 10^5
• 1 \le k \le n
• 1 \le x_i \le 10^9

Example

Input:

5 3
2 4 7 3 5

Output:

8

Explanation: An optimal division is [2,4],[7],[3,5] where the sums of the subarrays are 6,7,8. The largest sum is the last sum 8.