eolymp
bolt
Try our new interface for solving problems
Problems

Segment Sum

Segment Sum

Time limit 2 seconds
Memory limit 64 MiB

A segment of a sequence a_1, a_2, …, a_N is a sequence a_i, a_{i+1}, …, a_j for some 1ijN. Given an integer sequence consider a set of all its segments, ordered by the sum of elements. Your task is to find the sum of elements of K-th segment in this order (0-based). In this problem two segments are considered different, if one of their ends does not coincide. So actually it can be a multiset, for example for sequence 2, 2 all its different segments are {2}, {2}, {2,2}. Therefore any sequence of length N will have exactly N(N+1)/2 segments. For given example, their sums will be 2, 2, 4 in order.

Input data

First line of input contains two integer numbers N and K – length of the sequence and 0-based number of interesting segment (1N10^5, 0K < N(N+1)/2). Second line contains N integers a_1, a_2, …, a_N – the elements of the sequence (-10^9a_i10^9).

Output data

Sum of elements of K-th segment in this order (0-based).

Examples

Input example #1
3 0
1 4 -3
Output example #1
-3
Source International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011