justright

Problem Description

Gug is going on a mushroom-collecting holiday. He has a list of N cities that he wants to visit, and each city i has A_i mushrooms within it.

Gug has to choose a consecutive segment of cities in his list to visit, and he will collect all the mushrooms within the cities he visits. Therefore, he has N*(N+1)/2 possible holidays, and each will yield a specific number of mushrooms.

Gug knows that too little mushrooms are bad, and too much mushrooms are also bad. He wants to go on a holiday such that the number of mushrooms collected is the Kth largest possible among all the holidays he could have chosen.

Find the number of mushrooms collected in the holiday that Gug chooses to go on.

Input

The first line of input will contain two integers, N and K.
The second line of input will contain N integers, representing the array A.

Output

The output should contain one line with one integer, the number of mushrooms collected by Gug in his holiday.

Limits

For all subtasks: 1 ≤ K ≤ N*(N+1)/2, 1 ≤ A_i ≤ 10⁹.

Subtask 1 (27%): 1 ≤ N ≤ 1000.

Subtask 2 (8%): 1 ≤ N ≤ 200000, K = 1.

Subtask 3 (9%): 1 ≤ N ≤ 200000, K = N*(N+1)/2.

Subtask 4 (20%): 1 ≤ N ≤ 200000, A_i = 1.

Subtask 5 (36%): 1 ≤ N ≤ 200000.

Subtask 6 (0%): Sample Testcases.

Sample Input 1

5 6
1 2 3 4 5

Sample Output 1

9

Sample Input 2

5 1
3 1 4 1 5

Sample Output 2

14