Problem Description

You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $ N $.
For a non-empty contiguous subsequence $ B $ of $ A $, define the score of $ B $ as the absolute value of the sum of its elements.
There are a total of $\frac{N(N+1)}{2}$ non-empty contiguous subsequences of $ A $. Calculate the $ K $-th smallest score among all these subsequences.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ A_1 $ $ A_2 $ $\dots$ $ A_N $

Output Format

Output the $ K $-th smallest score.

Sample Input and Output

Sample Input #1

2 2
2 -3

Sample Output #1

2

Sample Input #2

5 10
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output #2

3000000000

Sample Input #3

7 22
3 -1 4 -1 5 -9 2

Sample Output #3

5

Notes/Hints

Constraints

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq K \leq \frac{N(N+1)}{2}$
• $-10^9 \leq A_i \leq 10^9$
• All inputs are integers.

Sample Explanation 1

The non-empty contiguous subsequences of $ A $ and their scores are as follows:
- The score of the sequence $ (A_1) $ is $ |2| = 2 $.
- The score of the sequence $ (A_2) $ is $ |-3| = 3 $.
- The score of the sequence $ (A_1, A_2) $ is $ |2 + (-3)| = 1 $.

Sample Explanation 2

Note that the answer may not fit into a 32-bit integer.

见题面 Input 部分

见题面 Output 部分