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

Example 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~.