Array Division

You are given an array containing $nn$ positive integers.

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

Input

The first input line contains two integers $nn$ and $kk$: the size of the array and the number of subarrays in the division.

The next line contains $nn$ integers $x_1,x_2,\dots ,x_{n}x\_1,x\_2,\backslash ldots,x\_n$: the contents of the array.

Output

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