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 Ai 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 ≤ Ai ≤ 109.
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, Ai = 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