Given an array with ~n~ elements, what is the ~k~-th largest sub array sum. (A subarray sum is the sum of all elements within a continuous section of the array).

Input

The first line contain integers ~n~ and ~k~. The second line contains ~n~ integers ~a_1,\dots,a_n~, the elements of the array.

Output

Output the ~k~-th largest subarray sum.

Constraints

• ~1 \le n \le 10^4~
• ~1 \le k \le \frac{n(n+1)}{2}~
• ~1 \le a_i \le 10^9~

Example 1

Input

10 1
7 7 4 6 3 8 9 8 5 1

Output

58

Example 2

Input

3 4
8 10 4

Output

10

Example 3

Input

5 6
3 6 9 8 4

Output

18