Array Division

• Time limit: 1.00 s
• Memory limit: 512 MB

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$.